A study on token digraphs

DOI10.1016/J.DISC.2025.114951MaRDI QIDQ6857925zbMATH OpenFDO

Authors Cristina G. Fernandes, Carla Negri Lintzmayer, Juan Pablo Peña, Giovanne Santos, Ana Laura Trujillo-Negrete, José Zamora

Publication date 16 February 2026

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114951

Review text

The manuscript introduces and develops the theory of \(k\)-token digraphs \(F_k(D)\), a directed analogue of the symmetric \(k\)-th power (token) graphs. For a digraph \(D\) of order \(n\) and \(1\le k\le n-1\), the vertex set of \(F_k(D)\) is the family of \(k\)-subsets of \(V(D)\); there is an arc \((A,B)\) in \(F_k(D)\) precisely when \(A\) and \(B\) differ in a single element and that element moves along an arc of \(D\). The paper systematically investigates structural, combinatorial and algorithmic properties of \(F_k(D)\), including: (i) the structure of strong components and criteria for strong connectivity and acyclicity; (ii) kernels and the computational complexity of kernel existence in \(F_2(D)\); (iii) unilaterality; (iv) directed girth and circumference; (v) Eulerianity and Hamiltonicity; (vi) bidirected clique number; and (vii) acyclic partitions and the dichromatic number. An appendix treats the chromatic number of 2-token graphs in the undirected setting and formulates a conjecture.\N\NMain results (concise)\N\begin{itemize}\N\item[1.] Strong components. Theorem 3.3 gives a complete description of the strong component digraph \(\mathrm{SC}(F_k(D))\): its vertices are integer vectors \((k_1,\dots,k_t)\) with \(\sum k_i=k\) (where \(C_1,\dots,C_t\) are the strong components of \(D\)), and arcs correspond to feasible \((i,j)\)-moves compatible with arcs of \(\mathrm{SC}(D)\). More precisely, let \(D\) be a digraph and \(C_1,\dots,C_t\) be a topological ordering of its strongly connected components. The strong component digraph \(\mathrm{SC}(F_k(D))\) is isomorphic to the \(DAG\) whose vertex set is \(V_k(|C_1|,\dots,|C_t|)\) and with an arc from \((k_1,\dots,k_t)\) to \((k'_1,\dots,k'_t)\) if and only if there are indices \(i < j\) such that there is an \((i, j)\)-move from \((k_1,\dots,k_t)\) to \((k'_1,\dots,k'_t)\) and there is an arc from \(C_i\) to \(C_j\) in \(\mathrm{SC}(D)\). Corollaries include that digraph \(F_k(D)\) is strongly connected iff \(D\) is strongly connected, and that digraph \(F_k(D)\) is acyclic iff \(D\) is acyclic (Corollaries 3.4 and 3.5).\N\item[2.] Kernels and complexity. The parity obstruction for kernels transfers to token digraphs: if \(D\) has no odd cycle then \(F_k(D)\) has no odd cycle and hence a unique kernel (Theorem 4.2 together with Richardson's theorem: If \(D\) is a digraph with no odd cycles, then \(F_k(D)\) has no odd cycles). The authors show that deciding whether \(F_2(D)\) has a kernel is NP-complete (Theorem 4.3: The problem of, given a digraph \(D\), deciding whether \(F_2(D)\) has a kernel is NP-complete) by adapting Chvátal's reduction and reducing from NAE-3-SAT.\N\item[3.] Unilaterality. Theorem 5.2 characterizes when \(F_k(D)\) is unilateral: for \(2\le k\le n-2\), \(F_k(D)\) is unilateral iff \(D\) is unilateral and either the number \(t\) of strong components satisfies \(t\le 2\) or \(t=3\) with the middle component of size one. More precisely, let \(D\) be a digraph of order \(n\) with \(C_1,\dots,C_t\) being its strongly connected components, and let \(k\) be an integer such that\N\(2\le k\le n-2\). Then \(F_k(D)\) is unilateral if and only if \(D\) is unilateral and either \(t \le 2\) or \(t = 3\) with \(|C_2|=1\).\N\item[4.] Girth and circumference. Directed girth is preserved: \(g(F_k(D))=g(D)\) (Theorem 6.1: For every digraph \(D\) on \(n\) vertices and for each \(k \in \{1,2,\dots,n -1\}\), \(g(D) = g(F_k(D))\) and \(c(D) \le c(F_k(D))\)). Theorem 6.2 gives lower bounds on \(c(F_k(D))\) in terms of \(c(D)\) and constructs long cycles in \(F_k(D)\). More precisely, let \(D\) be a digraph on \(n\) vertices with \(c(D) \ge 5\) and \(2\le k \le n-3\). Let \(r =2\) if \(k=2\) and \(r =\min\{\max\{k,n-k\},c(D)-3\}\) otherwise. Then \(c(F_k(D)) \ge r c(D)\).\N\item[5.] Eulerianity and Hamiltonicity. Eulerianity is equivalent between \(D\) and \(F_k(D)\) for every \(k\) (Theorem 7.1: For every natural \(k\), the digraph \(D\) is Eulerian if and only if \(F_k(D)\) is Eulerian). Examples show Hamiltonicity is not preserved in either direction.\N\item[6.] Bidirected clique number and dichromatic number. The bidirected clique number of \(F_k(D)\) is expressed in terms of that of \(D\) via the clean-graph construction and the known undirected token-graph clique formula (Theorem 8.3: For any digraph \(D\) of order \(n\) and \(1\le k \le n-1\), it holds that \(\overleftrightarrow{\omega}(F_k(D))=\mathrm{min}\{\overleftrightarrow{\omega}(D),\mathrm{max}\{n-k+1,k+1\}\}\)). The inequality \(\overleftrightarrow{\chi}(F_k(D))\le \overleftrightarrow{\chi}(D)\) is proved (Theorem 9.1: For any digraph \(D\), \(\overleftrightarrow{\chi}(F_k(D))\le \overleftrightarrow{\chi}(D)\)), with corollaries combining this with known bounds relating dichromatic number, girth and circumference.\N\item[7.] Appendix (undirected case). Conjecture A.1 (\(\chi (F_2(G)) < \chi (G)\) if and only if \(G = K_n\) for even \(n\)) and supporting evidence for the chromatic number of 2-token graphs are provided; several classes of graphs are analyzed and two lemmas (A.2: For every graph \(G\) on \(n\ge 5\) vertices, with \(\chi(G)=4\) and a universal vertex \(u\), \(\chi (F_2(G)=4\); A.3: For every odd \(k\), \(\chi(F_2(M(C_k))) =4\)) are proved for 4-critical families.\N\end{itemize}\N\NThe proofs presented in the manuscript (as supplied) are logically coherent and use standard, appropriate combinatorial and digraph-theoretic techniques. Key structural results (Lemmas 3.1 and 3.2 and Theorem 3.3) are proved constructively: Lemma 3.1 uses induction on the size of the symmetric difference of configurations; Lemma 3.2 decomposes strongly connected components of \(F_k(D)\) as Cartesian products of token digraphs of the strong components of \(D\); Theorem 3.3 then assembles these facts to describe \(\mathrm{SC}(F_k(D))\). These structural results are sound and underpin many subsequent theorems.\N\NThe NP-completeness proof for kernel existence in \(F_2(D)\) adapts Chvátal's classical reduction carefully. The reduction is described in sufficient detail: the construction of the digraph \(D\) from a 3-SAT formula, the addition of a universal sink \(u\), the partition of the token graph into two parts (configurations containing \(u\) and those not containing \(u\)), and the correspondence between kernels in \(F_2(D)\) and special kernels in \(D'\) are all argued with explicit case analysis. The gadget analysis for the subdigraphs of \(F_2(D)\) (e.g., the subdigraph \(Z\) in the proof) is convincing, and the contradiction arguments are clear.\N\NThe degree-counting argument for Eulerianity (Theorem 7.1) is straightforward and correct: the authors relate in- and out-degrees of a configuration \(A\) in \(F_k(D)\) to sums of degrees in \(D\) and the number of internal arcs \(e(A)\), and deduce equivalence of the Eulerian property.\N\NThe cycle-preservation arguments (Theorem 6.1) are natural: cycles in \(D\) lift to cycles in \(F_k(D)\) by moving tokens around the cycle, and cycles in \(F_k(D)\) project to cycles in \(D\) by collecting arcs traversed by tokens. The lower-bound construction for circumference (Theorem 6.2) is explicit and combinatorial; the case analysis is clear.\N\NThe manuscript is well organized: definitions and basic properties are stated early (Section 2), followed by sections each devoted to a specific invariant. Figures and concrete examples (e.g., Figs.\ 1--7 and the appendix figures) effectively illustrate phenomena such as non-preservation of kernels and Hamiltonicity. Notation is standard and consistently used.\N\NThe authors situate their contributions relative to the literature on undirected token graphs (symmetric powers) and prior directed variants. They acknowledge an independent master's thesis [\textit{J. J. Fernández-Velázquez}, Policías y ladrones sobre digráficas de fichas (Cops and Robbers on digraphic cards). Universidad Nacional Autónoma de México (M.Sc. Thesis) (2022)] that introduces token digraphs and proves related results (strong connectivity, diameter, existence of cycles). The present manuscript claims complementarity and lists additional contributions (complete characterization of strong connectivity via \(\mathrm{SC}(D)\), results on directed girth/circumference/Eulerianity, bidirected clique number, dichromatic number, and NP-completeness for kernels).\N\NThe paper treats a broad set of classical digraph invariants in the token-digraph setting, giving a coherent and useful picture of how the token construction interacts with directed structure. The complete description of \(\mathrm{SC}(F_k(D))\) (Theorem 3.3) is a natural and powerful structural result that underlies many subsequent deductions.\NThe NP-completeness result for kernel existence in \(F_2(D)\) is a significant and nontrivial algorithmic contribution.\NSeveral results are supported by explicit constructions (long cycles, kernel correspondences, gadget analyses), which enhance reproducibility and understanding. The use of the clean graph and the transfer of known undirected token-graph results (e.g., clique formula) are well executed.

Cites work

This page was built for publication: A study on token digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6857925)