Lovász conjecture

It says: Originally László Lovász stated the problem in the opposite way, but this version became standard.

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.

For directed Cayley graphs (digraphs) the Lovász conjecture is false.

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.

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.

The Lovász conjecture was also established for random generating sets of size