David Bremner ; Olivier Devillers ; Marc Glisse ; Sylvain Lazard ; Giuseppe Liotta ; Tamara Mchedlidze ; Guillaume Moroz ; Sue Whitesides ; Stephen Wismath.
We study the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction? We prove that for any dimension $d\geq 2$, there is a set of $d + 1$ paths that does not admit a monotone simultaneous geometric embedding.
Section:
Discrete Algorithms
Arman Boyacı ; Tınaz Ekim ; Mordechai Shalom ; Shmuel Zaks.
Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT
graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the
EPT graph (i.e. the edge intersection graph) of P. These graphs have been
extensively studied in the literature. Given two (edge) intersecting paths in a
graph, their split vertices is the set of vertices having degree at least 3 in
their union. A pair of (edge) intersecting paths is termed non-splitting if
they do not have split vertices (namely if their union is a path). We define
the graph ENPT(P) of edge intersecting non-splitting paths of a tree, termed
the ENPT graph, as the graph having a vertex for each path in P, and an edge
between every pair of vertices representing two paths that are both
edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a
tree T and a set of paths P of T such that G=ENPT(P), and we say that <T,P> is
a representation of G.
Our goal is to characterize the representation of chordless ENPT cycles
(holes). To achieve this goal, we first assume that the EPT graph induced by
the vertices of an ENPT hole is given. In [2] we introduce three assumptions
(P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, we
define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize
the representations of ENPT holes that satisfy (P1), (P2), (P3).
In this work, we continue our work by relaxing these three assumptions one by
one. We characterize […]
Section:
Graph Theory
Yury Kartynnik ; Andrew Ryzhikov.
We study the computational complexity of several problems connected with
finding a maximal distance-$k$ matching of minimum cardinality or minimum
weight in a given graph. We introduce the class of $k$-equimatchable graphs
which is an edge analogue of $k$-equipackable graphs. We prove that the
recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge
2$. We provide a simple characterization for the class of strongly chordal
graphs with equal $k$-packing and $k$-domination numbers. We also prove that
for any fixed integer $\ell \ge 1$ the problem of finding a minimum weight
maximal distance-$2\ell$ matching and the problem of finding a minimum weight
$(2 \ell - 1)$-independent dominating set cannot be approximated in polynomial
time in chordal graphs within a factor of $\delta \ln |V(G)|$ unless
$\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (thereby
improving the NP-hardness result of Chang for the independent domination case).
Finally, we show the NP-hardness of the minimum maximal induced matching and
independent dominating set problems in large-girth planar graphs.
Section:
Graph Theory
C. Duffy ; T. F. Lidbetter ; M. E. Messinger ; R. J. Nowakowski.
We introduce a natural variant of the parallel chip-firing game, called the
diffusion game. Chips are initially assigned to vertices of a graph. At every
step, all vertices simultaneously send one chip to each neighbour with fewer
chips. As the dynamics of the parallel chip-firing game occur on a finite set
the process is inherently periodic. However the diffusion game is not obviously
periodic: even if $2|E(G)|$ chips are assigned to vertices of graph G, there
may exist time steps where some vertices have a negative number of chips. We
investigate the process, prove periodicity for a number of graph classes, and
pose some questions for future research.
Section:
Graph Theory
Jean-Florent Raymond.
The Erdős-Pósa property relates parameters of covering and packing of
combinatorial structures and has been mostly studied in the setting of
undirected graphs. In this note, we use results of Chudnovsky, Fradkin, Kim,
and Seymour to show that, for every directed graph $H$ (resp.
strongly-connected directed graph $H$), the class of directed graphs that
contain $H$ as a strong minor (resp. butterfly minor, topological minor) has
the vertex-Erdős-Pósa property in the class of tournaments. We also prove
that if $H$ is a strongly-connected directed graph, the class of directed
graphs containing $H$ as an immersion has the edge-Erdős-Pósa property in
the class of tournaments.
Section:
Graph Theory
Christopher Duffy ; Gary MacGillivray ; Éric Sopena.
We examine $t$-colourings of oriented graphs in which, for a fixed integer $k
\geq 1$, vertices joined by a directed path of length at most $k$ must be
assigned different colours. A homomorphism model that extends the ideas of
Sherk for the case $k=2$ is described. Dichotomy theorems for the complexity of
the problem of deciding, for fixed $k$ and $t$, whether there exists such a
$t$-colouring are proved.
Section:
Graph Theory
Dömötör Pálvölgyi.
The goal of this paper is to prove that several variants of deciding whether
a poset can be (weakly) embedded into a small Boolean lattice, or to a few
consecutive levels of a Boolean lattice, are NP-complete, answering a question
of Griggs and of Patkos. As an equivalent reformulation of one of these
problems, we also derive that it is NP-complete to decide whether a given graph
can be embedded to the two middle levels of some hypercube.
Section:
Graph Theory
Katarzyna Rybarczyk.
The construction of the random intersection graph model is based on a random
family of sets. Such structures, which are derived from intersections of sets,
appear in a natural manner in many applications. In this article we study the
problem of finding a Hamilton cycle in a random intersection graph. To this end
we analyse a classical algorithm for finding Hamilton cycles in random graphs
(algorithm HAM) and study its efficiency on graphs from a family of random
intersection graphs (denoted here by G(n,m,p)). We prove that the threshold
function for the property of HAM constructing a Hamilton cycle in G(n,m,p) is
the same as the threshold function for the minimum degree at least two. Until
now, known algorithms for finding Hamilton cycles in G(n,m,p) were designed to
work in very small ranges of parameters and, unlike HAM, used the structure of
the family of random sets.
Section:
Graph Theory
Hamid Kameli.
Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problem
of learning a hidden graph for some especial cases, such as hamiltonian cycle,
cliques, stars, and matchings. This problem is motivated by problems in
chemical reactions, molecular biology and genome sequencing.
In this paper, we present a generalization of this problem. Precisely, we
consider a graph G and a subgraph H of G and we assume that G contains exactly
one defective subgraph isomorphic to H. The goal is to find the defective
subgraph by testing whether an induced subgraph contains an edge of the
defective subgraph, with the minimum number of tests. We present an upper bound
for the number of tests to find the defective subgraph by using the symmetric
and high probability variation of Lovász Local Lemma.
Section:
Combinatorics
Shigeki Akiyama ; Victor Marsault ; Jacques Sakarovitch.
Every rational number p/q defines a rational base numeration system in which
every integer has a unique finite representation, up to leading zeroes. This
work is a contribution to the study of the set of the representations of
integers. This prefix-closed subset of the free monoid is naturally represented
as a highly non-regular tree. Its nodes are the integers, its edges bear labels
taken in {0,1,...,p-1}, and its subtrees are all distinct.
We associate with each subtree (or with its root n) three infinite words. The
bottom word of n is the lexicographically smallest word that is the label of a
branch of the subtree. The top word of n is defined similarly. The span-word of
n is the digitwise difference between the latter and the former.
First, we show that the set of all the span-words is accepted by an infinite
automaton whose underlying graph is essentially the same as the tree itself.
Second, we study the function that computes for all n the bottom word
associated with n+1 from the one associated with n, and show that it is
realised by an infinite sequential transducer whose underlying graph is once
again essentially the same as the tree itself.
An infinite word may be interpreted as an expansion in base p/q after the
radix point, hence evaluated to a real number. If T is a subtree whose root is
n, then the evaluations of the labels of the branches of T form an interval of
$\mathbb{R}$. The length of this interval is called the span of n and is equal
to the […]
Section:
Analysis of Algorithms
Benjamin Hackl ; Helmut Prodinger.
Stanley lists the class of Dyck paths where all returns to the axis are of
odd length as one of the many objects enumerated by (shifted) Catalan numbers.
By the standard bijection in this context, these special Dyck paths correspond
to a class of rooted plane trees, so-called Catalan-Stanley trees.
This paper investigates a deterministic growth procedure for these trees by
which any Catalan-Stanley tree can be grown from the tree of size one after
some number of rounds; a parameter that will be referred to as the age of the
tree. Asymptotic analyses are carried out for the age of a random
Catalan-Stanley tree of given size as well as for the "speed" of the growth
process by comparing the size of a given tree to the size of its ancestors.
Section:
Analysis of Algorithms
Mehri Javanian.
In a rooted tree, protected nodes are neither leaves nor parents of any leaves. They have some practical motivations, e.g., in organizational schemes, security models and social-network models. Protected node profile measures the number of protected nodes with the same distance from the root in rooted trees. For no rooted tree, protected node profile has been investigated so far. Here, we present the asymptotic expectations, variances, covariance and limiting bivariate distribution of protected node profile and non-protected internal node profile in random tries, an important data structure on words in computer science. Also we investigate the fraction of these expectations asymptotically. These results are derived by the methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization and depoissonization, saddle point method and singularity analysis.
Section:
Analysis of Algorithms
Julio Araujo ; Guillaume Ducoffe ; Nicolas Nisse ; Karol Suchan.
Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be […]
Section:
Graph Theory
Valentin Garnero ; Ignasi Sau.
A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such
that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total
dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on
general graphs when parameterized by the solution size. By the meta-theorem of
Bodlaender et al. [J. ACM, 2016], there exists a linear kernel for Total
Dominating Set on graphs of bounded genus. Nevertheless, it is not clear how
such a kernel can be effectively constructed, and how to obtain explicit
reduction rules with reasonably small constants. Following the approach of
Alber et al. [J. ACM, 2004], we provide an explicit kernel for Total Dominating
Set on planar graphs with at most $410k$ vertices, where $k$ is the size of the
solution. This result complements several known constructive linear kernels on
planar graphs for other domination problems such as Dominating Set, Edge
Dominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-Blue
Dominating Set.
Section:
Discrete Algorithms
Michael D. Barrus.
We define a weakly threshold sequence to be a degree sequence
$d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i
\geq k(k-1)+\sum_{i > k} \min\{k,d_i\} - 1$ for all positive $k \leq
\max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations of
the weakly threshold sequences. The weakly threshold graphs properly include
the threshold graphs and satisfy pleasing extensions of many properties of
threshold graphs. We demonstrate a majorization property of weakly threshold
sequences and an iterative construction algorithm for weakly threshold graphs,
as well as a forbidden induced subgraph characterization. We conclude by
exactly enumerating weakly threshold sequences and graphs.
Section:
Graph Theory
Grace Misereh ; Yuri Nikolayevsky.
A thrackle is a drawing of a graph in which each pair of edges meets
precisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing of
a graph on the plane cannot have more edges than vertices. We prove the
Conjecture for thrackle drawings all of whose vertices lie on the boundaries of
$d \le 3$ connected domains in the complement of the drawing. We also give a
detailed description of thrackle drawings corresponding to the cases when $d=2$
(annular thrackles) and $d=3$ (pants thrackles).
Section:
Graph Theory
Jessica Striker.
We generalize the notion of the toggle group, as defined in [P. Cameron-D.
Fon-der-Flaass '95] and further explored in [J. Striker-N. Williams '12], from
the set of order ideals of a poset to any family of subsets of a finite set. We
prove structure theorems for certain finite generalized toggle groups, similar
to the theorem of Cameron and Fon-der-Flaass in the case of order ideals. We
apply these theorems and find other results on generalized toggle groups in the
following settings: chains, antichains, and interval-closed sets of a poset;
independent sets, vertex covers, acyclic subgraphs, and spanning subgraphs of a
graph; matroids and convex geometries. We generalize rowmotion, an action
studied on order ideals in [P. Cameron-D. Fon-der-Flaass '95] and [J.
Striker-N. Williams '12], to a map we call cover-closure on closed sets of a
closure operator. We show that cover-closure is bijective if and only if the
set of closed sets is isomorphic to the set of order ideals of a poset, which
implies rowmotion is the only bijective cover-closure map.
Section:
Combinatorics
John Haslegrave.
An antimagic labelling of a graph $G$ is a bijection
$f:E(G)\to\{1,\ldots,E(G)\}$ such that the sums $S_v=\sum_{e\ni v}f(e)$
distinguish all vertices. A well-known conjecture of Hartsfield and Ringel
(1994) is that every connected graph other than $K_2$ admits an antimagic
labelling. Recently, two sets of authors (Arumugam, Premalatha, Ba\v{c}a \&
Semani\v{c}ová-Fe\v{n}ov\v{c}\'iková (2017), and Bensmail, Senhaji \&
Lyngsie (2017)) independently introduced the weaker notion of a local antimagic
labelling, where only adjacent vertices must be distinguished. Both sets of
authors conjectured that any connected graph other than $K_2$ admits a local
antimagic labelling. We prove this latter conjecture using the probabilistic
method. Thus the parameter of local antimagic chromatic number, introduced by
Arumugam et al., is well-defined for every connected graph other than $K_2$ .
Section:
Graph Theory
Michitaka Furuya.
In this paper, we characterize the sets $\mathcal{H}$ of connected graphs
such that there exists a constant $c=c(\mathcal{H})$ satisfying $\gamma (G)\leq
c$ for every connected $\mathcal{H}$-free graph $G$, where $\gamma (G)$ is the
domination number of $G$.
Section:
Graph Theory
Adam Borchert ; Narad Rampersad.
We show that the permutation complexity of the image of a Sturmian word by a
binary marked morphism is $n+k$ for some constant $k$ and all lengths $n$
sufficiently large.
Section:
Combinatorics
Kasper Szabo Lyngsie.
Let $S$ be a set of integers. A graph G is said to have the S-property if
there exists an S-edge-weighting $w : E(G) \rightarrow S$ such that any two
adjacent vertices have different sums of incident edge-weights. In this paper
we characterise all bridgeless bipartite graphs and all trees without the
$\{0,1\}$-property. In particular this problem belongs to P for these graphs
while it is NP-complete for all graphs.
Section:
Graph Theory
Melissa Keranen ; Juho Lauri.
A path in an edge-colored graph $G$ is rainbow if no two edges of it are
colored the same. The graph $G$ is rainbow-connected if there is a rainbow path
between every pair of vertices. If there is a rainbow shortest path between
every pair of vertices, the graph $G$ is strongly rainbow-connected. The
minimum number of colors needed to make $G$ rainbow-connected is known as the
rainbow connection number of $G$, and is denoted by $\text{rc}(G)$. Similarly,
the minimum number of colors needed to make $G$ strongly rainbow-connected is
known as the strong rainbow connection number of $G$, and is denoted by
$\text{src}(G)$. We prove that for every $k \geq 3$, deciding whether
$\text{src}(G) \leq k$ is NP-complete for split graphs, which form a subclass
of chordal graphs. Furthermore, there exists no polynomial-time algorithm for
approximating the strong rainbow connection number of an $n$-vertex split graph
with a factor of $n^{1/2-\epsilon}$ for any $\epsilon > 0$ unless P = NP. We
then turn our attention to block graphs, which also form a subclass of chordal
graphs. We determine the strong rainbow connection number of block graphs, and
show it can be computed in linear time. Finally, we provide a polynomial-time
characterization of bridgeless block graphs with rainbow connection number at
most 4.
Section:
Graph Theory
Selim Bahadır ; Didem Gözüpek.
Let $\gamma(G)$ and $\gamma_t(G)$ denote the domination number and the total
domination number, respectively, of a graph $G$ with no isolated vertices. It
is well-known that $\gamma_t(G) \leq 2\gamma(G)$. We provide a characterization
of a large family of graphs (including chordal graphs) satisfying $\gamma_t(G)=
2\gamma(G)$, strictly generalizing the results of Henning (2001) and Hou et al.
(2010), and partially answering an open question of Henning (2009).
Section:
Graph Theory
Sylwia Cichacz ; Jakub Przybyło.
For a given graph $G$, the least integer $k\geq 2$ such that for every
Abelian group $\mathcal{G}$ of order $k$ there exists a proper edge labeling
$f:E(G)\rightarrow \mathcal{G}$ so that $\sum_{x\in N(u)}f(xu)\neq \sum_{x\in
N(v)}f(xv)$ for each edge $uv\in E(G)$ is called the \textit{group twin
chromatic index} of $G$ and denoted by $\chi'_g(G)$. This graph invariant is
related to a few well-known problems in the field of neighbor distinguishing
graph colorings. We conjecture that $\chi'_g(G)\leq \Delta(G)+3$ for all graphs
without isolated edges, where $\Delta(G)$ is the maximum degree of $G$, and
provide an infinite family of connected graph (trees) for which the equality
holds. We prove that this conjecture is valid for all trees, and then apply
this result as the base case for proving a general upper bound for all graphs
$G$ without isolated edges: $\chi'_g(G)\leq 2(\Delta(G)+{\rm col}(G))-5$, where
${\rm col}(G)$ denotes the coloring number of $G$. This improves the best known
upper bound known previously only for the case of cyclic groups $\mathbb{Z}_k$.
Section:
Graph Theory
Brian Cloteaux.
We give a sufficient condition for a degree sequence to be graphic based on
its largest and smallest elements, length, and sum. This bound generalizes a
result of Zverovich and Zverovich.
Section:
Graph Theory
Zoltán Fülöp ; Luisa Herrmann ; Heiko Vogler.
We introduce weighted regular tree grammars with storage as combination of
(a) regular tree grammars with storage and (b) weighted tree automata over
multioperator monoids. Each weighted regular tree grammar with storage
generates a weighted tree language, which is a mapping from the set of trees to
the multioperator monoid. We prove that, for multioperator monoids canonically
associated to particular strong bi-monoids, the support of the generated
weighted tree languages can be generated by (unweighted) regular tree grammars
with storage. We characterize the class of all generated weighted tree
languages by the composition of three basic concepts. Moreover, we prove
results on the elimination of chain rules and of finite storage types, and we
characterize weighted regular tree grammars with storage by a new weighted
MSO-logic.
Section:
Automata, Logic and Semantics