Path Eccentricity and Forbidden Induced Subgraphs
Sylwia Cichacz, Claire Hilaire, Tomáš Masařík, Jana Masaříková, Martin Milanič · 2025
Read Path Eccentricity and Forbidden Induced Subgraphs by Sylwia Cichacz, Claire Hilaire, Tomáš Masařík, Jana Masaříková, Martin Milanič (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15747.txt.
Introduction
Sylwia Cichacz and Claire Hilaire lead a team characterizing graphs where some path passes near every vertex, and exactly which forbidden patterns force that to happen. Their paper appeared in two thousand twenty-five. Path eccentricity measures the worst distance from a chosen spine path. A classic result guarantees a fully spanning path when two small patterns are excluded.
Generalizing, they show that excluding two specific graphs caps eccentricity below any chosen bound. Conversely, a single excluded pattern works exactly when it hides inside two named families. Their proof leans on structural domination theory from earlier work. A polynomial-time algorithm finds the witnessing path robustly. The result also closes an open question from a recent paper. Such characterizations turn vague intuition about graph shape into checkable conditions. Algorithmic payoffs ride along with the theory.
Catalog record
| CREATOR | Sylwia Cichacz, Claire Hilaire, Tomáš Masařík, Jana Masaříková, Martin Milanič |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-15747
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Path Eccentricity and Forbidden Induced Subgraphs Sylwia Cichacz, Claire Hilaire, Tomáš Masařík, Jana Masaříková, Martin Milanič Abstract The path eccentricity of a connected graph G G is the minimum integer k k such that G G has a path such that every vertex is at distance at most k k from the path. A result of Duffus, Jacobson, and Gould from 1981 states that every connected { claw , net } \{\text{claw},\text{net}\} -free graph G G has a Hamiltonian path, that is, G G has path eccentricity 0 0 . Several more recent works identified various classes of connected graphs with path eccentricity at most 1 1 , or, equivalently, graphs having a spanning caterpillar, including connected P 5 P_{5} -free graphs, AT-free graphs, and biconvex graphs. Generalizing all these results, we apply the work on structural distance domination of Bacsó and Tuza [Discrete Math., 2012] and characterize, for every positive integer k k , graphs such that every connected induced subgraph has path eccentricity less than k k . More specifically, we show that every connected { S k , T k } \{S_{k},T_{k}\} -free graph has a path eccentricity less than k k , where S k S_{k} and T k T_{k} are two specific graphs of path eccentricity k k (a subdivided claw and the line graph of such a graph). As a consequence, every connected H H -free graph has path eccentricity less than k k if and only if H H is an induced subgraph of 3 P k 3P_{k} or P 2 k + 1 + P k − 1 P_{2k+1}+P_{k-1} . Our main result also answers an open question of Bastide, Hilaire, and Robinson [Discrete Math., 2025]. 1 Introduction A Hamiltonian path in a graph G is a path in G whose vertex set is V(G) ; a Hamiltonian cycle is defined similarly. The problems of determining whether a given graph has a Hamiltonian path or a Hamiltonian cycle are both NP -complete [ GJ79 , Kar72 ] , which motivates the search for sufficient conditions for their existence (see, e.g., the survey [ Gou14 ] ). One of the early results in the area is the following result of Duffus, Jacobson, and Gould [ DJG81 ] (see also [ She91 , BD03 , Kel06 ] ). Theorem 1.1 . Every connected \{ claw, net \} -free graph has a Hamiltonian path. Here, a claw is the complete bipartite graph K_{1,3} , the net is the graph obtained by appending a pendant edge to each vertex of the complete graph K_{3} , and, given a set \mathcal{F} of graphs, a graph G is said to be \mathcal{F} -free if G does not have an induced subgraph isomorphic to any member of \mathcal{F} . If \mathcal{F}=\{F\} for some graph F , we also say that G is F -free . The result of Theorem 1.1 is tight, since the claw and the net do not have a Hamiltonian path. Let us remark that, in general, if G is a graph that has a Hamiltonian path and H is a connected induced subgraph of G , then H may fail to have a Hamiltonian path. For example, if H is any n -vertex graph and G is a graph obtained from H by adding to it n new vertices fully adjacent to the vertices of H , then G has a Hamiltonian path, even though H may fail to have one. In particular, this construction could be applied to the the claw and the net. If we instead require that all connected induced subgraph have a Hamiltonian path, Theorem 1.1 implies the following characterization. Corollary 1.2 . For every graph G , the following statements are equivalent: • Every connected induced subgraph of G has a Hamiltonian path. • G is \{ claw, net \} -free. In 2023, Gómez and Gutiérrez [ GG23 ] generalized the concept of Hamiltonian paths by defining the notion of path eccentricity of graphs. Given a connected graph G and a path P in G , the eccentricity of P is the maximum distance from a vertex in G to a vertex in P . Hence, in particular, a path P has eccentricity 0 if and only if P is a Hamiltonian path, and P has eccentricity at most 1 if and only if P is dominating , that is, every vertex not in the path has a neighbor on the path. More generally, given an integer k\geqslant 0 , a path P is said to be k -dominating if it has eccentricity at most k . The path eccentricity of a connected graph G is denoted by \pe(G) and defined as the minimum eccentricity of a path in G . Hence, \pe(G)=0 if and only if G has a Hamiltonian path, and \pe(G)\leqslant 1 if and only if G has a dominating path. It is not difficult to see that a graph G has a dominating path if and only if G has a spanning caterpillar , that is, a spanning subgraph that is a caterpillar (a tree possessing a dominating path). Hence, understanding graphs that admit dominating paths is motivated by their applications to the graph burning and a variant of the cops and robber game. More precisely: • The burning graph conjecture (see Bonato, Janssen, and Roshanbin [ BJR16 ] ) is known to be true for graphs admitting a spanning caterpillar. • If a graph G admits a spanning caterpillar T , then the minimum number of cops sufficient for the cop player to win on the graph G against the robber moving at the speed of s is at most ps if G is a subgraph of the graph obtained from T by adding an edge between each pair of vertices that are at distance at most p in T (see Fomin et al. [ FGK+10 , Lemma 4] ). Since adding a universal vertex to any connected graph H results in a graph G with path eccentricity at most 1 , path eccentricity is not monotone under vertex deletion. Nevertheless, and in line with the above discussion preceding Corollary 1.2 , which characterizes graphs each connected induced subgraph of which has path eccentricity 0 , analogous questions can be addressed for higher values of path eccentricity. Question 1.3 . For a positive integer k , what are the graphs G such that each connected induced subgraph of G has path eccentricity at most k ? For each fixed k\geqslant 1 , there are two obstructions to path eccentricity less than k that can be obtained from the claw and the net, as follows. Given a positive integer k , let us denote by S_{k} the k -subdivided claw , that is, the graph obtained from the claw by replacing each of its edges with a path of length k (in particular, S_{1} is the claw). Furthermore, we denote by T_{k} the k -subdivided net , that is, the graph obtained by appending a path of length k to each vertex of the complete graph K_{3} (in particular, T_{1} is the net). See Figure 1 for an example. Figure 1: Visualization of graphs