Concept
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, but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples. 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, 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. 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 , the Petersen graph, the Coxeter graph and two graphs derived from the Petersen and Coxeter graphs by replacing each vertex with a triangle. 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. For directed Cayley graphs (digraphs) the Lovász conjecture is false. Various counterexamples were obtained by Robert Alexander Rankin. Still, many of the below results hold in this restrictive setting. 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.