Sparse pseudo‐random graphs are Hamiltonian

DOI10.1002/jgt.10065zbMath1028.05059arXivmath/0503745OpenAlexW4233896336WikidataQ105583230 ScholiaQ105583230MaRDI QIDQ4798125

Michael Krivelevich, Benjamin Sudakov

Publication date: 19 March 2003

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

random graphsHamiltonian graphsrandom Cayley graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eulerian and Hamiltonian graphs (05C45)

Related Items (41)

Packing tight Hamilton cycles in 3-uniform hypergraphs ⋮ Matching number, Hamiltonian graphs and magnetic Laplacian matrices ⋮ On the Hamiltonicity of random bipartite graphs ⋮ Random Latin square graphs ⋮ Extremal problems on the Hamiltonicity of claw-free graphs ⋮ Hamiltonicity in prime sum graphs ⋮ Embedding cycles in finite planes ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Finding any given 2‐factor in sparse pseudorandom graphs efficiently ⋮ Eigenvalues and [a,b‐factors in regular graphs] ⋮ Hamilton cycles in highly connected and expanding graphs ⋮ A survey on Hamilton cycles in directed graphs ⋮ Maximum degree and minimum degree spectral radii of some graph operations ⋮ Distance signless Laplacian spectral radius and Hamiltonian properties of graphs ⋮ Graph toughness from Laplacian eigenvalues ⋮ Spectral radius and Hamiltonian graphs ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ Expander graphs and gaps between primes ⋮ Signless Laplacian eigenvalues and circumference of graphs ⋮ Small spectral gap in the combinatorial Laplacian implies Hamiltonian ⋮ Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs ⋮ Sufficient conditions for Hamiltonian graphs in terms of (signless Laplacian) spectral radius ⋮ Embedding nearly-spanning bounded degree trees ⋮ Some problems on Cayley graphs ⋮ Powers of Hamilton cycles in pseudorandom graphs ⋮ On covering expander graphs by hamilton cycles ⋮ Spectral radius and Hamiltonicity of graphs ⋮ Hamilton cycles in random lifts of graphs ⋮ Local resilience of graphs ⋮ Additive patterns in multiplicative subgroups ⋮ Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs ⋮ Spectral radius and Hamiltonian properties of graphs ⋮ Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs ⋮ Spectral radius and Hamiltonicity of graphs with large minimum degree ⋮ A tight lower bound on the matching number of graphs via Laplacian eigenvalues ⋮ Hamilton cycles and paths in vertex-transitive graphs-current directions ⋮ Hamiltonian paths in Cayley graphs ⋮ Approximate Hamilton decompositions of random graphs ⋮ Edge-disjoint Hamilton cycles in random graphs ⋮ Unnamed Item ⋮ Spectral condition for Hamiltonicity of a graph

Cites Work

• Triangle factors in sparse pseudo-random graphs
• Unnamed Item

This page was built for publication: Sparse pseudo‐random graphs are Hamiltonian