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

Less than 1 year old · traced to

Let s≥1s\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 n≥nsn\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.

References

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).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.