The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs

ABSTRACT Let denote the minimum number of edges whose addition to results in a Hamiltonian graph, and let denote the minimum number of edges whose addition to results in a pancyclic graph. We study the distributions of in the context of binomial random graphs. Letting , we prove that there exists a function of order such that, if with , then with high probability . Let denote the number of degree vertices in . A trivial lower bound on is given by the expression . We show that in the random graph process with high probability there exist times , both of order , such that for every and for every . The time can be characterized as the smallest for which contains less than copies of a certain problematic subgraph. In particular, this implies that the hitting time for the existence of a Hamilton path is equal to the hitting time of with high probability. For the binomial random graph, this implies that if and , then, with high probability, . For completion to pancyclicity, we show that if and , then, with high probability, . Finally, we present a polynomial time algorithm such that, if and , then, with high probability, the algorithm returns a set of edges of size whose addition to results in a pancyclic (and therefore also Hamiltonian) graph.