Lovász's Hamilton-path conjecture for connected vertex-transitive graphs
Lovász's Hamilton-path conjecture for connected vertex-transitive graphs
Let be a connected vertex-transitive graph, meaning that for every there is an automorphism of mapping to . A Hamilton path is a path containing every vertex of .
Lovász's conjecture. Every connected vertex-transitive graph has a Hamilton path.
This classical conjecture asks whether vertex-transitivity guarantees a spanning path; it remains open in full generality, although substantial results are known for dense graphs and long cycles in general vertex-transitive graphs.
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
Mengyu Cao, Mei Lu and Xiamiao Zhao, “Matchings and Near-Optimal 2-Factor Packings in Percolated Vertex-Transitive Graphs”, arXiv:2607.20157 (2026).
Additional references
16 papers in this index state this conjecture (2003–2026). The statement above is taken from the most recent of them; the others are arXiv:2407.00646, arXiv:2402.06603, arXiv:2306.05574, arXiv:2303.05356, arXiv:1708.03476, arXiv:1612.07189, arXiv:1611.06974, arXiv:1409.4239, arXiv:1402.4268, arXiv:1101.2357, arXiv:1008.2193, arXiv:0907.5079, and 3 more.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.