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 László Lovász stated the problem in the opposite way, but this version became standard. In 1996, László 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 Donald 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

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 ${\displaystyle 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:

• ${\displaystyle a=(1,2,\dots ,n),b=(1,2)}$ (long cycle and a transposition).
• ${\displaystyle 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 ${\displaystyle \{1,2,..,n\}}$.
• ${\displaystyle 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:

• ${\displaystyle S=\{a,b\},(ab)^{2}=1}$ (Rankin generators)
• ${\displaystyle S=\{a,b,c\},a^{2}=b^{2}=c^{2}=[a,b]=1}$ (Rapaport–Strasser generators)
• ${\displaystyle S=\{a,b,c\},a^{2}=1,c=a^{-1}ba}$ (Pak–Radoičić generators^[6])
• ${\displaystyle S=\{a,b\},a^{2}=b^{s}=(ab)^{3}=1,}$ where ${\displaystyle |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 ${\displaystyle G}$ there exists a generating set of size at most ${\displaystyle \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 ${\displaystyle \Omega (\log ^{5}|G|)}$.^[8]

References