Hamilton cycles in dense vertex-transitive graphs

DOI10.1016/J.JCTB.2014.05.001zbMATH Open1301.05204arXiv1008.2193OpenAlexW3102222413MaRDI QIDQ462925FDOQ462925

Authors: Demetres Christofides, Jan Hladký, András Máthé 

Publication date: 22 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A famous conjecture of Lov'asz 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.

Full work available at URL: https://arxiv.org/abs/1008.2193

Recommendations

• Hamilton paths and cycles in vertex-transitive graphs of order \(6p\)
• An evidence for Lovász conjecture about Hamiltonian paths and cycles
• scientific article; zbMATH DE number 4150204
• Hamiltonicity of cubic Cayley graphs
• Hamiltonian cycles in vertex symmetric graphs of order \(2p^ 2\)

zbMATH Keywords

regularity lemmaHamilton cyclesLovász conjecture

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Embedding large subgraphs into dense graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Digraphs
• Quasi-random graphs
• Blow-up lemma
• Quasirandom Groups
• Title not available (Why is that?)
• The square of every two-connected graph is Hamiltonian
• Pseudo-random graphs
• Hamiltonian paths in Cayley graphs
• A method in graph theory
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Title not available (Why is that?)
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• An algorithmic version of the blow-up lemma
• Title not available (Why is that?)
• A semiexact degree condition for Hamilton cycles in digraphs
• Finding Hamilton cycles in robustly expanding digraphs
• Hamilton cycles and paths in vertex-transitive graphs-current directions
• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• Long cycles in vertex-transitive graphs
• The Algorithmic Aspects of the Regularity Lemma
• Packings in Dense Regular Graphs
• Title not available (Why is that?)
• A survey: Hamiltonian cycles in Cayley graphs

Cited In (15)

• Hamiltonian paths in odd graphs
• The robust component structure of dense regular graphs and applications
• Recent trends and future directions in vertex-transitive graphs
• On the conjecture of vertex-transitivity of DCell
• Hamiltonian cycles in vertex symmetric graphs of order \(2p^ 2\)
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Hamilton paths and cycles in vertex-transitive graphs of order \(6p\)
• Hamilton cycles in pseudorandom graphs
• Title not available (Why is that?)
• The diameters of some transition graphs constructed from Hamilton cycles
• Hamilton cycles in some vertex-transitive graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• On sufficient conditions for spanning structures in dense graphs
• Tight cycles and regular slices in dense hypergraphs
• Hamiltonian cycle problem in strong \(k\)-quasi-transitive digraphs with large diameter

This page was built for publication: Hamilton cycles in dense vertex-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q462925)