Conjecture 6. Every connected vertex-transitive graph contains a Hamilton path, and, except for five known examples, a Hamilton cycle.
Statement
Conjecture 6. Every connected vertex-transitive graph contains a Hamilton path, and, except for five known examples, a Hamilton cycle. As Cayley graphs are vertex-transitive and none of the five known exceptions in Conjecture 6 are Cayley graphs, Lovász’s conjecture implies the following earlier conjecture, posed in 1959, by Strasser [25]. Conjecture 7. Every connected Cayley graph is Hamiltonian. Conjecture 7 is known to be true when the underlying group is abelian, but the only progress towards the conjectures in general is a result of Babai \sqrt{ } [4] that every vertex-transitive n-vertex graph contains a cycle of length Ω( n) (see [10] for a recent improvement by DeVos) and a result of Christofides, Hladký and Máthé [7] that every vertex-transitive graph of linear minimum degree contains a Hamilton cycle. The “random version” of Conjecture 7 is a natural relaxation of the original problem. Alon and Roichman [3] showed that there is a constant C > 0 for which, for any group G, the Cayley graph generated by a random set S of C log |G| elements, Γ(G, S) say, is almost surely connected. Hence, an important instance of Conjecture 7 is to show that Γ(G, S) is almost surely Hamiltonian. This problem was also stated as a conjecture by Pak and Radoičić [23]. Since then, several papers have made progress on this problem. Krivelevich and Sudakov [19] showed that O(log5 n) generators suffice, Christofides and Markström [8] improved this bound to O(log3 n), and Glock, Munhá Correia, and Sudakov [14] further refined it to O(log5/3 n). The report passage is retained verbatim as the relevant context for this extracted problem.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.