Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph
Jorik Jooken, Carol T. Zamfirescu · 2026
Read Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph by Jorik Jooken, Carol T. Zamfirescu (2026) 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-2606-02279.txt.
Introduction
Jooken and Zamfirescu count Hamiltonian paths between two fixed vertices in graphs. A Hamiltonian path visits every vertex exactly once. The graphs here are traceable and ban a fixed induced subgraph F. At least one Hamiltonian path joins the two endpoints. The question is how many such paths must exist.
The count is studied as a function of graph order. A sharp dichotomy is the main result. If F is not an induced subgraph of a certain path family, counterexamples exist. Infinite families then have a unique Hamiltonian path between the endpoints. If F is such an induced subgraph, a lower bound holds. Every F-free traceable graph then has many Hamiltonian paths. The dividing line is exact in the theorem.
Catalog record
| CREATOR | Jorik Jooken, Carol T. Zamfirescu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02279
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph Jorik Jooken, Carol T. Zamfirescu Abstract For graphs G G and F F , we say that G G is F F -free if F F does not occur as an induced subgraph of G G . This paper is concerned with the following question: Given an F F -free graph G G having two vertices between which there exists at least one Hamiltonian path, how many Hamiltonian paths between these endpoints must exist (in terms of the order of G G )? Our main result shows that there exists a sharp dichotomy. More precisely, we show that if F F is not an induced subgraph of P 3 + s P 1 P_{3}+sP_{1} for any integer s ≥ 0 s\geq 0 , then there exists an infinite family of F F -free graphs having two vertices between which there exists a unique Hamiltonian path. On the other hand, we prove that if F F is an induced subgraph of P 3 + s P 1 P_{3}+sP_{1} for some integer s ≥ 0 s\geq 0 , then any F F -free graph having two vertices between which there exists a Hamiltonian path contains exponentially many such paths between these two vertices. Our proofs use Ramsey-theoretic methods, a result on the existence of two vertices with low degree in graphs containing a unique Hamiltonian cycle, a path variant of Thomassen’s red-independent weakly green-dominating sets, and a structural analysis of Hamiltonian paths in P 3 + s P 1 P_{3}+sP_{1} -free graphs. As an algorithmic consequence we obtain that for every fixed s ≥ 1 s\geq 1 , given a Hamiltonian s P 1 sP_{1} -free graph together with a Hamiltonian cycle, one can decide in linear time whether a second Hamiltonian cycle exists and construct one if it does. Keywords: Number of Hamiltonian paths, F F -free graphs 2020 Mathematics Subject Classification: 05C38; 05C45; 05C69; 05C75 1 Introduction A graph is Hamiltonian if it contains a spanning cycle, referred to as a Hamiltonian cycle . Similarly, a graph is traceable if it contains a spanning path, referred to as a Hamiltonian path . Hamiltonicity and traceability are among the most studied notions in graph theory. One is often not only interested in the existence of a Hamiltonian cycle or path, but also in the extent to which additional assumptions force richer behavior. For example, such assumptions may guarantee cycles of many different lengths, a second Hamiltonian cycle or many Hamiltonian paths between prescribed vertices. A famous example is a problem that was stated by Erdős [ 10 ] in the seventies: Given a Hamiltonian graph G on n vertices for which the independence number \alpha(G)\leq s , how large does one have to make n (in terms of s ) to guarantee that G contains a cycle of each length in \{3,4,\ldots,n\} ? Erdős [ 10 ] showed that \Omega(s^{4}) vertices suffice, but conjectured that \Omega(s^{2}) vertices should already be enough. This lower bound was systematically improved over the last 50 years (see e.g. [ 6 , 12 , 13 ] ) until the conjecture was recently proven by Draganić, Munhá Correia and Sudakov [ 8 ] in a strong form by showing that (2+o(1))s^{2} vertices suffice. In the current paper, we will be interested in the number of pairwise distinct Hamiltonian paths between prescribed vertices (and also obtain results on Hamiltonian cycles as direct corollaries). A famous example that deals with a similar notion is Sheehan’s conjecture [ 16 ] stating that every Hamiltonian 4 -regular graph contains at least two Hamiltonian cycles. For integers s\geq 2 and t\geq 1 , a graph is an [s,t] -graph if every subgraph induced by s vertices contains at least t edges. This notion generalizes the independence number: for a graph G , we have \alpha(G)\leq s if and only if G is an [s+1,1] -graph. Several recent results investigate Hamiltonian properties under such conditions. Cheng [ 4 ] gives additional background and further Hamiltonian-type results on [s,t] -graphs; in particular, he proved that for every k -connected [k+1,2] -graph there exists a Hamiltonian path between each two distinct vertices, apart from one explicit exceptional family. Li and Zhan [ 14 ] recently showed that every Hamiltonian [4,2] -graph on at least eight vertices contains a second Hamiltonian cycle. The results that we will present in the current paper have as a corollary that for all integers s\geq 2 and t\geq 1 , a Hamiltonian [s,t] -graph contains exponentially many Hamiltonian cycles. The current paper is situated in another popular setting that generalizes the bounded independence number setting. For graphs G and F , we say that G is F -free if G does not contain F as an induced subgraph. We write the disjoint union of G and F as G+F and the disjoint union of s copies of F is written as sF . The path on n vertices is denoted by P_{n} . Therefore, for a graph G we have \alpha(G)\leq s if and only if G is (s+1)P_{1} -free. For vertices a,b\in V(G) , an ab -path is a path with endpoints a and b . Our main result is as follows. Theorem 1 . Let F be a graph. If F is not an induced subgraph of P_{3}+sP_{1} for any integer s\geq 0 , then there exists an infinite family of F -free graphs, each with two vertices between which there exists a unique Hamiltonian path. On the other hand, if F is an induced subgraph of P_{3}+sP_{1} for some integer s\geq 0 , then there exists a constant c_{s}=2^{\Theta(s)} such that every F -free graph G having a Hamiltonian path between two vertices a,b\in V(G) contains at least 2^{\left\lfloor\frac{n}{c_{s}}\right\rfloor} distinct Hamiltonian ab -paths. We also derive an algorithmic consequence for a search problem involving Hamiltonian cycles. More precisely, for every fixed integer s\geq 1 , we show that the problem Second Hamiltonian cycle in sP_{1} -free graphs can be solved in linear time: given an sP_{1} -free graph G together with a Hamiltonian cycle, the algorithm either constructs a second Hamiltonian cycle or correctly concludes that none exists. 2 Infinite families of F -free graphs having a unique Hamiltonian path between prescribed vertices A graph G is called uniquely Hamiltonian if G contains exactly one Hamiltonian cycle. We first observe the existence of two infinite families of uniquely Hamiltonian F -free graphs for particular graphs F . The next observation follows immediately by considering large enough cycles. Observation 2 . Let F be a graph that contains a cycle or a vertex with at least three neighbors. Then there exists an infinite family of F -free graphs with a unique Hamiltonian cycle. Observation 3 . There exists an infinite family of 2P_{2} -free graphs with a unique Hamiltonian cycle. Proof. Let k\geq 3 be an integer. Let G be a graph on 2k vertices obtained by taking a clique K_{k} on k vertices, duplicating each edge from a Hamiltonian cycle \mathfrak{C} in K_{k} and subdividing once each edge in \mathfrak{C} ( G is also known as a sun graph