Hamilton completion and the path cover number of sparse random graphs

DOI10.1016/j.ejc.2024.103934arXiv2210.11770MaRDI QIDQ6120895

Michael Krivelevich, Yahav Alon

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

Hamiltonian graphbinomial random graph model

Mathematics Subject Classification ID

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

Cites Work

• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On large matchings and cycles in sparse random graphs
• Hamiltonian circuits in random graphs
• A scaling limit for the length of the longest cycle in a sparse random graph
• Completion and deficiency problems
• Long paths and Hamiltonicity in random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• On the Method of Typical Bounded Differences
• Unnamed Item
• Unnamed Item

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