Almost all regular graphs are Hamiltonian

DOI10.1016/S0195-6698(83)80039-0zbMath0513.05048OpenAlexW2090700571MaRDI QIDQ1050368

Béla Bollobás

Publication date: 1983

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0195-6698(83)80039-0

zbMATH Keywords

regular graphsHamilton cycleslabelled vertices

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45)

Related Items

Finding Hamilton cycles in sparse random graphs, Dirac's theorem for random graphs, Depth first exploration of a configuration model, Updating the hamiltonian problem—A survey, Maximal paths in random dynamic graphs, Partitioning random graphs into large cycles, Hamilton Cycles in Random Regular Digraphs, Local resilience for squares of almost spanning cycles in sparse random graphs, The integer homology threshold in 𝑌_{𝑑}(𝑛,𝑝), On the Hamiltonicity of the \(k\)-regular graph game, Hamilton cycles in the union of random permutations, Graph theory (algorithmic, algebraic, and metric problems), Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs, Hamiltonicity in random directed graphs is born resilient, Spanning trees in random graphs, On the existence of Hamiltonian cycles in a class of random graphs, Elements of a theory of computer simulation. I, Hamiltonicity in random graphs is born resilient, Random near-regular graphs and the node packing problem

Cites Work

• Limit distribution for the existence of Hamiltonian cycles in a random graph
• The number of matchings in random regular graphs and bipartite graphs
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Hamiltonian circuits in random graphs
• The asymptotic number of labeled graphs with given degree sequences
• On the existence of Hamiltonian cycles in a class of random graphs
• Regular factors of regular graphs
• For How Many Edges is a Graph Almost Certainly Hamiltonian?
• The Asymptotic Number of Unlabelled Regular Graphs
• Almost all Graphs have a Spanning Cycle
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item