Lovász conjecture

From Wikipedia, the free encyclopedia
  (Redirected from Lovasz conjecture)
Jump to: navigation, search

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[edit]

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[edit]

Hamiltonian cycle[edit]

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 K2, 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[edit]

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 and a generating set . Thus one can ask for which and the conjecture holds rather than attack it in full generality.

Directed Cayley graph[edit]

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[edit]

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 is a symmetric group, there are many attractive generating sets. For example, the Lovász conjecture holds in the following cases of generating sets:

  • (long cycle and a transposition).
  • (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 .

Stong has shown that the conjecture holds for the Cayley graph of the wreath product Zm wr Zn 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 Z2 wr Zn.[5]

General groups[edit]

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

  • (R.A. Rankin generators)
  • (Rapaport-Strasser generators)
  • (Pak-Radoičić generators[6])
  • where (here we have (2,s,3)-presentation, Glover-Marušič theorem[7]).

Finally, it is known that for every finite group there exists a generating set of size at most 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 .[8]


  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
  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, MR 522721, doi:10.1016/0012-365X(78)90059-6 .
  5. ^ Stong, Richard (1987), "On Hamiltonian cycles in Cayley graphs of wreath products", Discrete Mathematics, 65 (1): 75–80, MR 891546, doi:10.1016/0012-365X(87)90212-3 .
  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.