Hamilton cycles in dense vertex-transitive graphs

DOI10.1016/J.JCTB.2014.05.001MaRDI QIDQ462925zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

regularity lemmaHamilton cyclesLovász conjecture

Mathematics Subject Classification ID

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

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.

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\)

Cites work

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

Cited in

(15)

• Hamiltonian paths in odd graphs
• The robust component structure of dense regular graphs and applications
• Hamiltonian cycles in vertex symmetric graphs of order \(2p^ 2\)
• On the conjecture of vertex-transitivity of DCell
• Recent trends and future directions in vertex-transitive graphs
• 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
• scientific article; zbMATH DE number 4150204 (Why is no real title available?)
• Hamilton cycles in pseudorandom graphs
• 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)