This section of Discrete Mathematics & Theoretical Computer Science seeks high quality articles on structural and algorithmic aspects of graphs and related discrete mathematical models. We particularly seek topics with an intersection between discrete mathematics and computer science. We handle submissions in all areas of finite graph theory.
Editors:Pierre Aboulker, Jørgen Bang-Jensen, Bostjan Bresar, Maria Chudnovsky, Ueverton dos Santos Souza, Louis Esperet, Daniel Goncalves, Adriana Hansberg, John Haslegrave, Frederic Havet, Michael Anthony Henning, Michael Anthony Henning, Jing Huang, Felix Joos, Tomas Kaiser, Tomas Kaiser, Ken-ichi Kawarabayashi, Peter Keevash, Jaehoon Kim, William Lochet, Christophe Paul, Alexandre Pinlou, Alexey Pokrovskiy, Dieter Rautenbach, Jean-Sébastien Sereni, Katherine Staden, Raphael Steiner, Zoltán Szigeti, Zoltán Szigeti, Sebastian Wiederrecht, Anders Yeo
Editors:Pierre Aboulker, Jørgen Bang-Jensen, Bostjan Bresar, Maria Chudnovsky, Ueverton dos Santos Souza, Louis Esperet, Daniel Goncalves, Adriana Hansberg, John Haslegrave, Frederic Havet, Michael Anthony Henning, Michael Anthony Henning, Jing Huang, Felix Joos, Tomas Kaiser, Tomas Kaiser, Ken-ichi Kawarabayashi, Peter Keevash, Jaehoon Kim, William Lochet, Christophe Paul, Alexandre Pinlou, Alexey Pokrovskiy, Dieter Rautenbach, Jean-Sébastien Sereni, Katherine Staden, Raphael Steiner, Zoltán Szigeti, Zoltán Szigeti, Sebastian Wiederrecht, Anders Yeo
Notions of graph similarity provide alternative perspective on the graph isomorphism problem and vice-versa. In this paper, we consider measures of similarity arising from mismatch norms as studied in Gervens and Grohe: the edit distance $δ_{\mathcal{E}}$, and the metrics arising from $\ell_p$-operator norms, which we denote by $δ_p$ and $δ_{|p|}$. We address the following question: can these measures of similarity be used to design polynomial-time approximation algorithms for graph isomorphism? We show that computing an optimal value of $δ_{\mathcal{E}}$ is \NP-hard on pairs of graphs with the same number of edges. In addition, we show that computing optimal values of $δ_p$ and $δ_{|p|}$ is \NP-hard even on pairs of $1$-planar graphs with the same degree sequence and bounded degree. These two results improve on previous known ones, which did not examine the restricted case where the pairs of graphs are required to have the same number of edges. Finally, we study similarity problems on strongly regular graphs and prove some near optimal inequalities with interesting consequences on the computational complexity of graph and group isomorphism.
Let $D$ be a digraph of order $p\geq5$ with minimum degree at least $p-1$ and with minimum semi-degree at least $p/2-1$. In his excellent and renowned paper, ``Long Cycles in Digraphs" (Proc. London Mathematical Society (3), 42 (1981), Thomassen fully characterized the following for $p=2n+1$: (i) $D$ has a cycle of length at least $2n$; and (ii) $D$ is Hamiltonian. Motivated by this result, and building on some of the ideas in Thomassen's paper, we investigated the Hamiltonicity (when $p$ is even) and pancyclcity (when $p$ is arbitrary) such digraphs. We have given a complete description of whether such digraphs are Hamiltonian ($p$ is even), are pancyclic ($p$ is arbitrary). Since the proof is very long, we have divided it into three parts. In this paper, we provide a full description of the following: (iii) for $k=3$ and $k=4$, the digraph $D$ contains a cycle of length $k$; and (iv) the digraph $D$ contains a pre-Hamiltonian cycle, i.e. a cycle of length $p-1$.
The relation between local structure and global cycle properties is a classical topic in graph theory. A graph $G$ is locally linear if $G[N(v)]$ is a path for every $v\in V(G)$. It is locally Hamiltonian or locally traceable if every vertex neighborhood induces a Hamiltonian or traceable graph, respectively. Earlier work by Pareek and Skupień, Skupień, Davies and Thomassen, Asratian and Oksimets, and de Wet and van Aardt studied extremal questions for these related graph classes. We prove that the minimum order of a nonhamiltonian locally linear graph is $12$ and that, for every integer $n\geq 12$, the minimum size of such a graph of order $n$ is $2n$. We also prove that every nontraceable locally linear graph of order $n$ has at least $2n+3$ edges. 16 pages, 4 figures
Rui Li, Gregory Gutin, He Zhang, Zhao Wang, Xiaoyan Zhang, Yaping Mao
Abstract
Cartesian product networks are always regarded as a tool for ``combining'' two given networks with established properties to obtain a new one that inherits properties from both. For a graph $F=(V,E)$ and a set $S\subseteq V(F)$ of at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner tree connecting $S$} (or simply, \emph{an $S$-tree}) is a subgraph $T=(V',E')$ of $F$ that is a tree with $S\subseteq V'$. For $S\subseteq V(F)$ and $|S|\geq 2$, the {\it generalized local edge-connectivity} $λ(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $F$. For an integer $k$ with $2\leq k\leq n$, the {\it generalized $k$-edge-connectivity} $λ_k(F)$ of a graph $F$ is defined as $λ_k(F)=\min\{λ(S)\,|\,S\subseteq V(F) \ and \ |S|=k\}$.In this paper, we give sharp upper and lower bounds for $λ_k(G\Box H)$, where $\Box$ is the Cartesian product operation, and $G,H$ are two graphs. 14 pages; 3 figures
The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any $P_4$ with two colors (bicolored). This problem was introduced by Grünbaum (1973) together with the acyclic coloring of graphs, where bicolored cycles are avoided. In this paper, we study a generalization of this problem, by considering proper vertex coloring on graphs forbidding bicolored paths of a fixed length, which was initially discussed by Alon, McDiarmid, and Reed (1991). Here, we study this problem on products of two paths. We show that at least 4 colors are needed to properly color the product of paths, $P_m\square P_n$, avoiding a bicolored $P_k,$ unless $n<k-2$ or $m<k-2.$ With this result, the above question is settled for all $k$ on 2-dimensional grids.
Whitney proved that 3-connected planar graphs admit a unique embedding on the sphere. In contrast, Enami investigated embeddings of 3-connected cubic planar graphs on non-spherical surfaces with non-negative Euler characteristic. He established that such an embedding exists if and only if the dual graph contains a particular subgraph. Here, strong embeddings are investigated motivated by the cycle double cover conjecture and the relation to triangulated surfaces. We provide a complete characterization of strong embeddings on the projective plane, the torus, and the Klein bottle in terms of a distinguished subset of Enami's subgraphs. This characterization not only deepens the structural understanding of graph embeddings on non-spherical surfaces, but also establishes a robust foundation for computing cycle double covers. As a direct consequence, we derive explicit criteria that determine when a graph does not admit a strong embedding on these surfaces-offering new tools for both theoretical analysis and algorithmic applications.
In 1977, Chung, Chung and Liu generalized the definition of the Ramsey number. They introduced the $s$-chromatic Ramsey number as follows. Let $1\leq s< t$ be integers and let $A_{1}, A_{2}, \dots, A_{c}$ be subsets with size $s$ of $[t]$, where $c= {t\choose s}$. For given graphs $G_{1}, G_{2}, \dots, G_{c}$, the {\it $s$-chromatic Ramsey number} $r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum positive integer $N$ such that every $t$-coloring of $E(K_{N})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$. The {\it star-critical $s$-chromatic Ramsey number} $r_{*}^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum integer $\ell$ such that every $t$-coloring of the edges in $K_{N}- E(K_{1, N- 1- \ell})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$, where $N= r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$. If $G_{1}= G_{2}= \dots= G_{c}= G$, then we simplify them to $r^{s, t}(G)$ (also called the {\it weakened Ramsey number}) and $r^{s, t}_{*}(G)$, respectively. In this paper, we determine all the values of $r^{s, t}(K_{1, m})$ and $r_{*}^{s, t}(K_{1, m})$, and part of the value of $r^{s, t}(K_{1, m_{1}}, K_{1, m_{2}}, \dots, K_{1, m_{c}})$.
Given a class of (undirected) graphs $\mathcal{C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{C}$. We show that deciding if a tournament has a $\mathcal{C}$-FAS is NP-complete when $\mathcal{C}$ is the class of all forests. We are motivated by connections between $\mathcal{C}$-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.
The famous Tower of Hanoi puzzle involves moving $n$ discs of distinct sizes from one of $p\geq 3$ pegs (traditionally $p=3$) to another of the pegs, subject to the constraints that only one disc may be moved at a time, and no disc can ever be placed on a disc smaller than itself. Much is known about the Hanoi graph $H_p^n$, whose $p^n$ vertices represent the configurations of the puzzle, and whose edges represent the pairs of configurations separated by a single legal move. In a previous paper, the present authors presented nearly tight asymptotic bounds of $O((p-2)^n)$ and $Ω(n^{(1-p)/2}(p-2)^n)$ on the treewidth of this graph for fixed $p \geq 3$. In this paper we show that the upper bound is tight, by giving a matching lower bound of $Ω((p-2)^n)$ for the expansion of $H_p^n$. 18 pages, 5 figures
Csilla Bujtás, Tanja Dravec, Michael A. Henning, Sandi Klavžar
Abstract
The isolation game is played on a graph $G$ by two players who take turns playing a vertex such that if $X$ is the set of already played vertices, then a vertex can be selected only if it dominates a vertex from a nontrivial component of $G \setminus N_G[X]$, where $N_G[X]$ is the set of vertices in $X$ or adjacent to a vertex in $X$. Dominator wishes to finish the game with the minimum number of played vertices, while Staller has the opposite goal. The game isolation number $ι_{\rm g}(G)$ is the number of moves in the Dominator-start game where both players play optimally. If Staller starts the game the invariant is denoted by $ι_{\rm g}'(G)$. In this paper, $ι_{\rm g}(C_n)$, $ι_{\rm g}(P_n)$, $ι_{\rm g}'(C_n)$, and $ι_{\rm g}'(P_n)$ are determined for all $n$. It is proved that there are only two graphs that attain equality in the upper bound $ι_{\rm g}(G) \le \frac{1}{2}|V(G)|$, and that there are precisely eleven graphs which attain equality in the upper bound $ι_{\rm g}'(G) \le \frac{1}{2}|V(G)|$. For trees $T$ of order at least three it is proved that $ι_{\rm g}(T) \le \frac{5}{11}|V(T)|$. A new infinite family of graphs $G$ is also constructed for which $ι_{\rm g}(G) = ι_{\rm g}'(G) = \frac{3}{7}|V(G)|$ holds.
The Spanning Tree Congestion (STC) problem is the following NP-hard problem: given a graph $G$, construct a spanning tree $T$ of $G$ minimizing its maximum edge congestion where the congestion of an edge $e\in T$ is the number of edges $uv$ in $G$ such that the unique path between $u$ and $v$ in $T$ passes through $e$; the optimal value for a given graph $G$ is denoted $STC(G)$. It is known that every spanning tree is an $n/2$-approximation for the STP problem. A long-standing problem is to design a better approximation algorithm. Our contribution towards this goal is an $O(Δ\cdot\log^{3/2}n)$-approximation algorithm where $Δ$ is the maximum degree in $G$ and $n$ the number of vertices. For graphs with a maximum degree bounded by a polylog of the number of vertices, this is an exponential improvement over the previous best approximation. Our main tool for the algorithm is a new lower bound on the spanning tree congestion which is of independent interest. Denoting by $hb(G)$ the hereditary bisection of $G$ which is the maximum bisection width over all subgraphs of $G$, we prove that for every graph $G$, $STC(G)\geq Ω(hb(G)/Δ)$. Final DMTCS version. 9 pages
Let $(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on $X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ induced on the elements in $E$ is connected. We consider the problem of constructing a support for hypergraphs defined by connected subgraphs of a host graph. For a graph $G=(V,E)$, let $\mathcal{H}$ be a set of connected subgraphs of $G$. Let the vertices of $G$ be partitioned into two sets the \emph{terminals} $\mathbf{b}(V)$ and the \emph{non-terminals} $\mathbf{r}(V)$. We define a hypergraph on $\mathbf{b}(V)$, where each $H\in\mathcal{H}$ defines a hyperedge consisting of the vertices of $\mathbf{b}(V)$ in $H$. We also consider the problem of constructing a support for the \emph{dual hypergraph} - a hypergraph on $\mathcal{H}$ where each $v\in \mathbf{b}(V)$ defines a hyperedge consisting of the subgraphs in $\mathcal{H}$ containing $v$. In fact, we construct supports for a common generalization of the primal and dual settings called the \emph{intersection hypergraph}. As our main result, we show that if the host graph $G$ has bounded genus and the subgraphs in $\mathcal{H}$ satisfy a condition of being \emph{cross-free}, then there exists a support that also has bounded genus. Our results are a generalization of the results of Raman and Ray (Rajiv Raman, Saurabh Ray: Constructing Planar Support for Non-Piercing Regions. Discret. Comput. Geom. 64(3): 1098-1122 (2020)). Our techniques imply a unified analysis for packing and covering problems for hypergraphs defined on surfaces of bounded genus. We also describe applications of our results for hypergraph colorings.
In an oriented graph $\overrightarrow{G}$, the inversion of a subset $X$ of vertices is the operation that reverses the orientation of all arcs with both end-vertices in $X$. The inversion graph of a graph $G$, denoted by $\mathcal{I}(G)$, is the graph whose vertices are orientations of $G$ in which two orientations $\overrightarrow{G_1}$ and $\overrightarrow{G_2}$ are adjacent if and only if there is an inversion transforming $\overrightarrow{G_1}$ into $\overrightarrow{G_2}$.The inversion diameter of a graph $G$ is the diameter of its inversion graph $\mathcal{I}(G)$, denoted by $\mathrm{diam}(\mathcal{I}(G))$.Havet, Hörsch, and Rambaud~(2024) first proved that for $G$ of treewidth $k$, $\mathrm{diam}(\mathcal{I}(G)) \le 2k$, and that there are graphs of treewidth $k$ with inversion diameter $k+2$.In this paper, we construct graphs of treewidth $k$ with inversion diameter $2k$, which implies that the previous upper bound $\mathrm{diam}(\mathcal{I}(G)) \le 2k$ is tight.Moreover, for graphs with maximum degree $Δ$, Havet, Hörsch, and Rambaud~(2024) proved $\mathrm{diam}(\mathcal{I}(G)) \le 2Δ-1$ and conjectured that $\mathrm{diam}(\mathcal{I}(G)) \le Δ$. We prove the conjecture when $Δ=3$ with the help of computer calculations.
Locating-dominating codes have been studied widely since their introduction in the 1980s by Slater and Rall. In this paper, we concentrate on vertices that must belong to all minimum locating-dominating codes in a graph. We call them \emph{min-forced vertices}. We show that the number of min-forced vertices in a connected nontrivial graph of order $n$ is bounded above by $\frac{2}{3}\left(n -γ^{LD}(G)\right)$, where $γ^{LD}(G)$ denotes the cardinality of a minimum locating-dominating code. This implies that the maximum ratio between the number of min-forced vertices and the order of a connected nontrivial graph is at most $\frac{2}{5}$. Moreover, both of these bounds can be attained. In particular, the ratio $\frac{2}{5}$ is obtained by paths of order $5m$ having a unique minimum locating-dominating code of size $2m$. Furthermore, as a natural extension, we determine the number of different minimum locating-dominating codes in paths of all orders. In addition, we show that deciding whether a vertex is min-forced is co-NP-hard. 22 pages, 6 figures
A new model for domination reconfiguration is introduced which combines the properties of the preexisting token addition/removal (TAR) and token sliding (TS) models. The vertices of the TARS-graph correspond to the dominating sets of $G$, where two vertices are adjacent if and only if they are adjacent via either the TAR reconfiguration rule or the TS reconfiguration rule. While the domination reconfiguration graph obtained by using only the TAR rule (sometimes called the dominating graph) will never have a Hamilton cycle, we show that for some classes of graphs $G$, by adding a relatively small number of token sliding edges, the resulting graph is not only hamiltonian, but is in fact pancyclic. In particular, if the underlying graphs are trees, complete graphs, or complete multipartite graphs, we show that their TARS-graphs will be pancyclic. Notably, we prove that if the TARS-graphs of $G$ and $H$ are pancyclic, then the TARS-graph of the join $G \vee H$ will also be pancyclic. We conclude by posing the question: Are all TARS-graphs pancyclic? 15 pages, 4 figures
Pierre Aboulker, Nacim Oijid, Robin Petit, Mathis Rocton, Christopher-Lloyd Simon
Abstract
Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order. The degreewidth of a digraph is the minimum over all ordering of the maximum degree of the backedge graph. We answer an open question by Keeney and Lokshtanov [WG 2024], proving that it is \NP-hard to determine whether an oriented graph has degreewidth at most $1$, which settles the last open case for oriented graphs. We complement this result with a general discussion on parameters defined using backedge graphs and their relations to classical parameters.
Alex S. A. Alochukwu, Audace A. V. Dossou-Olory, Fadekemi J. Osaye, Valisoa R. M. Rakotonarivo, Shashank Ravichandran, Sarah J. Selkirk, Hua Wang, Hays Whitlatch
Abstract
The rank (also known as protection number or leaf-height) of a vertex in a rooted tree is the minimum distance between the vertex and any of its leaf descendants. We consider the sum of ranks over all vertices (known as the security) in binary trees, and produce a classification of families of binary trees for which the security is maximized. In addition, extremal results relating to maximum rank among all vertices in families of trees is discussed. This work is an output of the American Mathematical Society's Mathematics Research Community (MRC): Trees in Many Contexts
In this paper, we consider induced subgraphs of the Hamming graph $H(n,3)$. We show that if $U \subseteq \mathbb{Z}_3^n$ and $U$ induces a subgraph of $H(n,3)$ with maximum degree at most $1$ then 1. If $U$ is disjoint from a maximum size independent set of $H(n,3)$ then $|U| \leq 3^{n-1}+1$. Moreover, all such $U$ with size $3^{n-1}+1$ are isomorphic to each other. 2. For $n \geq 6$, there exists such a $U$ with size $|U| = 3^{n-1}+18$ and this is optimal for $n = 6$. 3. If $U \cap \{x, x+e_1, x+2e_1\} \ne ϕ$ for all $x \in \mathbb{Z}_3^n$ then $|U| \leq 3^{n-1} + 81$. 41 pages. This is the journal version of our paper
The study of homomorphisms of $(n,m)$-graphs, that is, adjacency preserving vertex mappings of graphs with $n$ types of arcs and $m$ types of edges was initiated by Nešetřil and Raspaud in 2000. Later, some attempts were made to generalize the switch operation that is popularly used in the study of signed graphs, and study its effect on the above mentioned homomorphism. In this article, we too provide a generalization of the switch operation on $(n,m)$-graphs, which to the best of our knowledge, encapsulates all the previously known generalizations as special cases. We approach the study of homomorphisms with respect to the switch operation axiomatically. We prove some fundamental results that are essential tools in the further study of this topic. In the process of proving the fundamental results, we have provided yet another solution to an open problem posed by Klostermeyer and MacGillivray in 2004. We also prove the existence of a categorical product for $(n,m)$-graphs with respect to a particular class of generalized switch which implicitly uses category theory. This is a counter intuitive solution as the number of vertices in the Categorical product of two $(n,m)$-graphs on $p$ and $q$ vertices has a multiple of $pq$ many vertices, where the multiple depends on the switch. This solves an open question asked by Brewster in the PEPS 2012 workshop as a corollary. We also provide a way to calculate the product explicitly, and prove general properties of the product. We define the analog of chromatic number for $(n,m)$-graphs with respect to generalized switch and explore the interrelations between chromatic numbers with respect to different switch operations. We find the value of this chromatic number for the family of forests using group theoretic notions. 21 pages
In 1978, Anderson and White asked whether there is a decomposition of $K_{12}$ into two graphs, one planar and one toroidal. Using theoretical arguments and a computer search of all maximal planar graphs of order 12, we show that no such decomposition exists. We further show that if $G$ is planar of order 12 and $H\subseteq\overline{G}$ is toroidal, then $H$ has at least two fewer edges than $\overline{G}$. A computer search found all 123 unique pairs $\left(G,H\right)$ that make this an equality. 9 pages
, Jørgen Bang-Jensen