A graph is vertex-transitive if its automorphism group acts transitively upon its vertices.
A Hamiltonian path is a path that visits each vertex exactly once.

Lovász conjecture: Every finite connected vertex-transitive graph contains a Hamiltonian path.
This conjecture is open since almost 50 years.

A connected graph is $2$-connected if it remains connected whenever any vertex is removed.
Question: Is Lovász conjecture known in the $2$-connected case (or $k$-connected for $k$ large enough)?


The vertex connectivity of a vertex-transitive graph with valency $k$ is at least $2(k+1)/3$ (Mader/Watkins). So if you prove the conjecture for 3-connected graphs, you've done them all.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.