The completion numbers of hamiltonicity and pancyclicity in random graphs
Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 66(2), e21286.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Alon, Yahav;
Anastos, MichaelISTA
Department
Abstract
Let μ(G) denote the minimum number of edges whose addition to G results in a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n. Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability, μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p) and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability, the algorithm returns a set of edges of size μ(G) whose addition to G results in a pancyclic (and therefore also Hamiltonian) graph.
Publishing Year
Date Published
2025-03-01
Journal Title
Random Structures and Algorithms
Publisher
Wiley
Acknowledgement
The authors would like to express their thanks to the referees of the article for their valuable input towards improving the presentation of our result. This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.
Volume
66
Issue
2
Article Number
e21286
ISSN
eISSN
IST-REx-ID
Cite this
Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 2025;66(2). doi:10.1002/rsa.21286
Alon, Y., & Anastos, M. (2025). The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.21286
Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” Random Structures and Algorithms. Wiley, 2025. https://doi.org/10.1002/rsa.21286.
Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity in random graphs,” Random Structures and Algorithms, vol. 66, no. 2. Wiley, 2025.
Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity in random graphs. Random Structures and Algorithms. 66(2), e21286.
Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs.” Random Structures and Algorithms, vol. 66, no. 2, e21286, Wiley, 2025, doi:10.1002/rsa.21286.
All files available under the following license(s):
Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0):
Main File(s)
File Name
2025_RandomStruc_Alon.pdf
549.24 KB
Access Level

Date Uploaded
2025-03-25
MD5 Checksum
6067747e805fa356d560dc45f2a89918
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2304.03710