Conjecture on unique Hamiltonian cycles in P4+sP1P_4+sP_1-free graphs

From papers

Let s1s\geq 1 be an integer. Let PkP_k denote the path on kk vertices, and let sP1sP_1 denote the disjoint union of ss isolated vertices. A graph is P4+sP1P_4+sP_1-free if it has no induced subgraph isomorphic to P4+sP1P_4+sP_1. Let GG be a Hamiltonian graph on nn vertices, meaning that GG contains a spanning cycle. It is uniquely Hamiltonian if it contains exactly one Hamiltonian cycle.

Conjecture. There exists a constant nsn_s depending on ss such that GG is not uniquely Hamiltonian whenever nnsn\geq n_s.

This conjecture predicts that, for each fixed ss, sufficiently large Hamiltonian P4+sP1P_4+sP_1-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

No solutions have been posted yet.