Hamilton cycles in dense vertex-transitive graphs

Christofides, Demetres, Hladky, Jan and Máthé, András (2014) Hamilton cycles in dense vertex-transitive graphs. Journal of Combinatorial Theory, Series A, 109 . pp. 34-72. ISSN 0097-3165

[thumbnail of Author Accepted Manuscript]
PDF (Author Accepted Manuscript) - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.


Official URL: http://dx.doi.org/10.1016/j.jctb.2014.05.001


A famous conjecture of Lovász states that every connected vertex-transitive graph contains a Hamilton path. In this article we confirm the conjecture in the case that the graph is dense and sufficiently large. In fact, we show that such graphs contain a Hamilton cycle and moreover we provide a polynomial time algorithm for finding such a cycle.

Repository Staff Only: item control page