Lovász conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

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

The original article of Lovász stated the result in the opposite, 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, therefore that 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[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 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:

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:

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

  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. ^ Michael Krivelevich and Benny Sudakov Sparse Pseudo-Random Graphs are Hamiltonian