On the existence of Hamiltonian cycles in a class of random graphs
作者： T.I. Fenner , A.M. Frieze
DOI: 10.1016/0012-365X(83)90046-8
关键词: Random graph 、 Combinatorics 、 Hamiltonian path problem 、 Mathematics 、 Random regular graph 、 Graph 、 Hamiltonian (quantum mechanics) 、 Hamiltonian path 、 Digraph 、 Discrete mathematics
摘要: A digraph with n vertices and fixed outdegree m is generated randomly so that each such equally likely to be chosen. We consider the probability of existence a Hamiltonian cycle in graph obtained by ignoring arc orientation. show there exists (=<23) tending 1 as tends infinity.
elsevier.com
sci-hub.se 参考文章(7)
T. I. Fenner, A. M. Frieze, On the connectivity of randomm-orientable graphs and digraphs Combinatorica. ,vol. 2, pp. 347- 359 ,(1982) , 10.1007/BF02579431
T.I Fenner, A.M Frieze, Hamiltonian Cycles in Random Regular Graphs Journal of Combinatorial Theory, Series B. ,vol. 37, pp. 103- 112 ,(1984) , 10.1016/0095-8956(84)90066-2
L. Pósa, Hamiltonian circuits in random graphs Discrete Mathematics. ,vol. 14, pp. 359- 364 ,(1976) , 10.1016/0012-365X(76)90068-6
David W. Walkup, Matchings in random regular bipartite digraphs Discrete Mathematics. ,vol. 31, pp. 59- 64 ,(1980) , 10.1016/0012-365X(80)90172-7
János Komlós, Endre Szemerédi, Limit distribution for the existence of Hamiltonian cycles in a random graph Discrete Mathematics. ,vol. 306, pp. 1032- 1038 ,(1983) , 10.1016/0012-365X(83)90021-3
Béla Bollobás, Almost all Regular Graphs are Hamiltonian European Journal of Combinatorics. ,vol. 4, pp. 97- 106 ,(1983) , 10.1016/S0195-6698(83)80039-0
Colin McDiarmid, General percolation and random graphs Advances in Applied Probability. ,vol. 13, pp. 40- 60 ,(1981) , 10.2307/1426466