On the connectivity of randomm-orientable graphs and digraphs

作者： T. I. Fenner , A. M. Frieze

关键词:

摘要: We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex.

参考文章(5)

David W. Walkup, On the Expected Value of a Random Assignment Problem SIAM Journal on Computing. ,vol. 8, pp. 440- 442 ,(1979) , 10.1137/0208036

Leo Katz, Probability of Indecomposability of a Random Mapping Function Annals of Mathematical Statistics. ,vol. 26, pp. 512- 517 ,(1955) , 10.1214/AOMS/1177728496

T.I. Fenner, A.M. Frieze, On the existence of Hamiltonian cycles in a class of random graphs Discrete Mathematics. ,vol. 45, pp. 301- 305 ,(1983) , 10.1016/0012-365X(83)90046-8

P. Erdős, A. Rényi, On the strength of connectedness of a random graph Acta Mathematica Hungarica. ,vol. 12, pp. 261- 267 ,(1964) , 10.1007/BF02066689

Martin D. Kruskal, The Expected Number of Components Under a Random Mapping Function American Mathematical Monthly. ,vol. 61, pp. 392- 397 ,(1954) , 10.1080/00029890.1954.11988482