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 File:Creative commons license with attribution.png 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

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

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.

Review text

Summary: We show that the probability that a random graph \(G\sim G(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

• A note on Hamiltonian circuits
• Hamilton cycles in highly connected and expanding graphs
• Hamilton cycles, minimum degree, and bipartite holes
• 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?)
• 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

(21)

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

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)