Lovász conjecture

In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says:

Every finite connected vertex-transitive graph contains a Hamiltonian path.

Originally Lovász stated the problem in the opposite way, but this version became standard. In 1996 Babai published a conjecture sharply contradicting this conjecture,^[1] but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples.

Historical remarks

The problem of finding Hamiltonian paths in highly symmetric graphs is quite old. As Knuth describes it in volume 4 of The Art of Computer Programming,^[2] the problem originated in British campanology (bell-ringing). Such Hamiltonian paths and cycles are also closely connected to Gray codes. In each case the constructions are explicit.

Variants of the Lovász conjecture

Hamiltonian cycle

Another version of Lovász conjecture states that

Every finite connected vertex-transitive graph contains a Hamiltonian cycle except the five known counterexamples.

There are 5 known examples of vertex-transitive graphs with no Hamiltonian cycles (but with Hamiltonian paths): the complete graph K₂, the Petersen graph, the Coxeter graph and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle.^[3]

Cayley graphs

None of the 5 vertex-transitive graphs with no Hamiltonian cycles is a Cayley graph. This observation leads to a weaker version of the conjecture:

Every finite connected Cayley graph contains a Hamiltonian cycle.

The advantage of the Cayley graph formulation is that such graphs correspond to a finite group $G$ and a generating set $S$. Thus one can ask for which $G$ and $S$ the conjecture holds rather than attack it in full generality.

Directed Cayley graph

For directed Cayley graphs (digraphs) the Lovász conjecture is false. Various counterexamples were obtained by R.A. Rankin. Still, many of the below results hold in this restrictive setting.

Special cases

A Hamiltonian path in the permutohedron, a Cayley graph of the symmetric group with Coxeter generators

Every directed Cayley graph of an abelian group has a Hamiltonian path; however, every cyclic group whose order is not a prime power has a directed Cayley graph that does not have a Hamiltonian cycle.^[4] In 1986, D. Witte proved that the Lovász conjecture holds for the Cayley graphs of p-groups. It is open even for dihedral groups, although for special sets of generators some progress has been made.

When group $G=S_{n}$ is a symmetric group, there are many attractive generating sets. For example, the Lovász conjecture holds in the following cases of generating sets:

• $a=(1,2,\dots ,n),b=(1,2)$ (long cycle and a transposition).
• $s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{{n-1}}=(n-1,n)$ (Coxeter generators). In this case a Hamiltonian cycle is generated by the Steinhaus–Johnson–Trotter algorithm.
• any set of transpositions corresponding to a labelled tree on $\{1,2,..,n\}$.
• $a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$

Stong has shown that the conjecture holds for the Cayley graph of the wreath product Z_m wr Z_n with the natural minimal generating set when m is either even or three. In particular this holds for the cube-connected cycles, which can be generated as the Cayley graph of the wreath product Z₂ wr Z_n.^[5]

General groups

For general finite groups, only a few results are known:

• $S=\{a,b\},(ab)^{2}=1$ (R.A. Rankin generators)
• $S=\{a,b,c\},a^{2}=b^{2}=c^{2}=[a,b]=1$ (Rapaport-Strasser generators)
• $S=\{a,b,c\},a^{2}=1,c=a^{{-1}}ba$ (Pak-Radoičić generators^[6])
• $S=\{a,b\},a^{2}=b^{s}=(ab)^{3}=1,$ where $|G|,s=2~mod~4$ (here we have (2,s,3)-presentation, Glover-Marušič theorem^[7]).

Finally, it is known that for every finite group $G$ there exists a generating set of size at most $\log _{2}|G|$ such that the corresponding Cayley graph is Hamiltonian (Pak-Radoičić). This result is based on classification of finite simple groups.

The Lovász conjecture was also established for random generating sets of size $\Omega (\log ^{5}|G|)$.^[8]

References

1. L. Babai, Automorphism groups, isomorphism, reconstruction, in Handbook of Combinatorics, Vol. 2, Elsevier, 1996, 1447-1540.
2. D. E. Knuth, The Art of Computer Programming, Vol. 4, draft of section 7.2.1.2.
3. Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
4. Holsztyński, W.; Strube, R. F. E. (1978), "Paths and circuits in finite groups", Discrete Mathematics, 22 (3): 263–272, doi:10.1016/0012-365X(78)90059-6, MR 522721.
5. Stong, Richard (1987), "On Hamiltonian cycles in Cayley graphs of wreath products", Discrete Mathematics, 65 (1): 75–80, doi:10.1016/0012-365X(87)90212-3, MR 891546.
6. I. Pak, R. Radoičić, Hamiltonian paths in Cayley graphs, 2002.
7. Henry Glover and Dragan Marusic Hamiltonicity of Cubic Cayley Graphs
8. Krivelevich, Michael; Sudakov, Benny (2003). "Sparse pseudo-random graphs are Hamiltonian". Journal of Graph Theory. 42: 17–33. doi:10.1002/jgt.10065.