Vol. 20 no. 1


1. Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$

Bremner, David ; Devillers, Olivier ; Glisse, Marc ; Lazard, Sylvain ; Liotta, Giuseppe ; Mchedlidze, Tamara ; Moroz, Guillaume ; Whitesides, Sue ; Wismath, Stephen.
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

Boyacı, Arman ; Ekim, Tınaz ; Shalom, Mordechai ; Zaks, Shmuel.
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 […]
Section: Graph Theory

3. On Minimum Maximal Distance-k Matchings

Kartynnik, Yury ; Ryzhikov, Andrew.
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 […]
Section: Graph Theory

4. A Variation on Chip-Firing: the diffusion game

Duffy, C. ; Lidbetter, T. F. ; Messinger, M. E. ; Nowakowski, R. J..
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

Raymond, Jean-Florent.
The Erdős-P\'osa 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\'osa 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\'osa property in the class of tournaments.
Section: Graph Theory