It is commonly believed that vertex-transitive graphs (and in particular Cayley graphs) tend to contain hamilton cycles. The only known connected vertex-transitive graphs without hamilton cycles are K1, K2, the Petersen graph, the Coxeter graph and two graphs obtained from these by `blowing-up’ each vertex to a triangle. Lovász has proposed the following
Problem (Lovász [3]): Prove that every connected vertex-transitive graph has a hamilton path.
In a survey article [1, Section 3.3], Babai is critical of the Lovász conjecture: “In my view these beliefs only reflect that Hamiltonicity obstacles are not well understood; and indeed, vertex-transitive graphs may provide a testing ground for the power of such obstacles.” At the same time he proposed the following counterstatement:
Conjecture (Babai, see [1]): There is a positive constant c such that there exist infinitely many connected vertex-transitive graphs (even Cayley graphs) G without cycles of length at least (1 - c)|V(G)|.
The above conjectures are not exactly opposite of each other in the sense that both of them could be false. For the current state of the art in this direction we refer to [1,2,4].
No real progress has been made on either of these conjectures in the sense that one would be able to say which of these conjectures is more likely to be true (although many interesting partial results have been proved). Therefore, I feel that the time has come to put forward some relaxed conjectures.
Let k be a positive integer and G a graph. A k-walk in G is a closed walk that visits every vertex of G and passes through any vertex at most k times.
Conjecture 1: Every connected vertex-transitive graph contains a 2-walk.
Conjecture 2: Every connected vertex-transitive graph contains a spanning tree of maximum degree 3.
It is easy to see that Lovasz' conjecture implies Conjecture 1, and that the latter implies Conjecture 2. As far as I believe that Conjecture 2 is true, I also believe that it may be possible that a spanning tree of maximum degree 3 would exist in which at most O(n1/2) vertices, where n = |V(G)|, have degree 3.
Following the conjecture of Babai, one could propose a counterconjecture (in which I personally do not believe):
Counterconjecture 3: For every positive integer k, there are infinitely many connected vertex-transitive graphs (even Cayley graphs) that do not contain a k-walk.
Of course, this statement is the same as claiming that for every positive integer k, there exists a vertex-transitive graph (a Cayley graph) that does not contain a k-walk.
[1] L. Babai, Automorphism groups, isomorphism, reconstruction, in Handbook of Combinatorics (R. L. Graham, M. Groetschel, and L. Lovasz, eds.), Elsevier, 1996.
[2] S. J. Curran, J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey, Discrete Math. 156 (1996), 1–18.
[3] L. Lovász, Problem 11, in “Combinatorial structures and their applications.” University of Calgary, Calgary, Alberta, Canada (1970), Gordon and Breach, New York.
[4] D. Witte, J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51 (1984) 293-304.
Send comments to Bojan.Mohar@uni-lj.si