Hamiltonian Closure in Random Graphs
作者： John Gimbel , David Kurtz , Linda Lesniak , Edward R. Scheinerman , John C. Wierman
DOI: 10.1016/S0304-0208(08)73048-2
关键词: Path graph 、 Mathematics 、 Complement graph 、 Combinatorics 、 Bound graph 、 Induced path 、 Graph power 、 Pancyclic graph 、 Graph toughness 、 Random regular graph 、 Discrete mathematics
摘要: The closure C * (C) of a graph G with n vertices is obtained by iteratively adding edges to between nonadjacent whose degrees sum at least n. We show that for almost all graphs edge probability 1/2, (G) complete graph, answering question posed Palmer.
sci-hub.se 参考文章(5)
Edgar M. Palmer, Unsolved Problems in the Theory of Random Graphs North-holland Mathematics Studies. ,vol. 144, pp. 227- 239 ,(1987) , 10.1016/S0304-0208(08)73058-5
J.A. Bondy, V. Chvatal, A method in graph theory Discrete Mathematics. ,vol. 15, pp. 111- 135 ,(1976) , 10.1016/0012-365X(76)90078-9
Oystein Ore, Note on Hamilton Circuits American Mathematical Monthly. ,vol. 67, pp. 55- ,(1960) , 10.2307/2308928
Herman Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations Annals of Mathematical Statistics. ,vol. 23, pp. 493- 507 ,(1952) , 10.1214/AOMS/1177729330
Béla Bollobás, Degree sequences of random graphs Discrete Mathematics. ,vol. 33, pp. 1- 19 ,(1981) , 10.1016/0012-365X(81)90253-3