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

CREATORSylwia Cichacz, Claire Hilaire, Tomáš Masařík, Jana Masaříková, Martin Milanič
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text