Random graph's Hamiltonicity is strongly tied to its minimum degree

DOI10.37236/8339MaRDI QIDQ2290359zbMATH OpenOpenAlexFDO

Authors Yahav Alon, Michael Krivelevich

Publication date 27 January 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1810.04987, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Hamilton cycleperfect matching

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We show that the probability that a random graph $GsimG(n,p)$ contains no Hamilton cycle is $(1+o(1))Pr(delta(G)<2)$ for all values of $p=p(n)$. We also prove an analogous result for perfect matchings.

Recommendations

• scientific article; zbMATH DE number 3922707
• scientific article; zbMATH DE number 3950585
• scientific article; zbMATH DE number 4193709
• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• Dirac's theorem for random graphs

Cites work

• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• A note on Hamiltonian circuits
• Hamilton cycles in highly connected and expanding graphs
• Hamilton cycles, minimum degree, and bipartite holes
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long paths and Hamiltonicity in random graphs
• On the existence of a factor of degree one of a connected random graph
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(16)

• Entropy bounds for perfect matchings and Hamiltonian cycles
• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• Random induced graphs
• Hamiltonicity of random graphs in the stochastic block model
• Hamilton cycles in random graphs with a fixed degree sequence
• Hamiltonian Berge cycles in random hypergraphs
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• Dirac-type theorems for inhomogenous random graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• Compatible Hamilton cycles in random graphs
• scientific article; zbMATH DE number 4114681 (Why is no real title available?)
• The global resilience of Hamiltonicity in \(G(n, p)\)
• Color‐biased Hamilton cycles in random graphs
• Dirac's theorem for random graphs

This page was built for publication: Random graph's Hamiltonicity is strongly tied to its minimum degree

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