 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 20 no. 1
1. Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$
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
2. Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II
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
3. On Minimum Maximal Distance-k Matchings
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. Note: This version (as compared to the journal submission) contains corrections to Section 4.
Section: Graph Theory
4. A Variation on Chip-Firing: the diffusion game
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
5. Hitting minors, subdivisions, and immersions in tournaments
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
6. A Study of $k$-dipath Colourings of Oriented Graphs
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
7. Weak embeddings of posets to the Boolean lattice
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
8. Finding Hamilton cycles in random intersection graphs
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
9. Non-adaptive Group Testing on Graphs
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
10. On subtrees of the representation tree in rational base numeration systems
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
11. Growing and Destroying Catalan-Stanley Trees
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
12. Protected node profile of Tries
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
13. On interval number in cycle convexity
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
14. A Linear Kernel for Planar Total Dominating Set
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
15. Weakly threshold graphs
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
16. Annular and pants thrackles
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
17. Rowmotion and generalized toggle groups
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
18. Proof of a local antimagic conjecture
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
19. Forbidden subgraphs for constant domination number
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
20. Permutation complexity of images of Sturmian words by marked morphisms
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
21. On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite graphs
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
22. Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs
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
23. On a Class of Graphs with Large Total Domination Number
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
24. Group twin coloring of graphs
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
25. A Sufficient Condition for Graphic Sequences with Given Largest and Smallest Entries, Length, and Sum
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
26. Weighted Regular Tree Grammars with Storage
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