3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .