Conjecture on unique Hamiltonian cycles in -free graphs
Conjecture on unique Hamiltonian cycles in -free graphs
Let be an integer. Let denote the path on vertices, and let denote the disjoint union of isolated vertices. A graph is -free if it has no induced subgraph isomorphic to . Let be a Hamiltonian graph on vertices, meaning that contains a spanning cycle. It is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle.
Conjecture. There exists a constant depending on such that is not uniquely Hamiltonian whenever .
This conjecture predicts that, for each fixed , sufficiently large Hamiltonian -free graphs must contain at least two Hamiltonian cycles. It is posed as a direction for future work, and the supplied text gives no resolution status.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Jorik Jooken and Carol T. Zamfirescu, “Counting Hamiltonian paths between prescribed vertices in traceable graphs with a forbidden induced subgraph”, arXiv:2606.02279 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.