Hamilton completion and the path cover number of sparse random graphs

DOI10.1016/J.EJC.2024.103934MaRDI QIDQ6120895zbMATH OpenFDO

Authors Yahav Alon, Michael Krivelevich

Publication date 26 March 2024

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

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

zbMATH Keywords

binomial random graph modelHamiltonian graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We prove that for every $varepsilon>0$ there is $c_0$ such that if $GsimG(n,c/n)$, $cge{c}_0$, then with high probability $G$ can be covered by at most $(1+varepsilon)cdotfrac12c{e}^{-c}cdotn$ vertex disjoint paths, which is essentially tight. This is equivalent to showing that, with high probability, at most $(1+varepsilon)cdotfrac12c{e}^{-c}cdotn$ edges can be added to $G$ to create a Hamiltonian graph.

Recommendations

• Hamiltonian completions of sparse random graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Optimal packings of Hamilton cycles in sparse random graphs
• How many random edges make a dense graph hamiltonian?

Cites work

• A scaling limit for the length of the longest cycle in a sparse random graph
• Completion and deficiency problems
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3878974 (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 large matchings and cycles in sparse random graphs
• On the method of typical bounded differences
• Probability Inequalities for Sums of Bounded Random Variables
• The probabilistic method

Cited in

(1)

• The completion numbers of Hamiltonicity and pancyclicity in random graphs

This page was built for publication: Hamilton completion and the path cover number of sparse random graphs

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