2023/04/07 by Yahav Alon, Alon, Yahav, Michael Anastos +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2304.03710
openalex publication_date 2023/04/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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:ℝ+→ [0,1] of order f(d) = (1)/(2)de-d+e-d+O(d6e-3d) such that, if G∼ G(n,p) with 20 ≤ d(n) ≤ 0.4 log n, 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) + \lceil (1)/(2)n1(G) \rceil. In the denser regime of random graphs, we show that if np-(1)/(3)log n - 2log log n → ∞ and G∼ G(n,p) then, with high probability, μ(G) = n0(G) + \lceil (1)/(2)n1(G) \rceil. 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.