Premium
Random graphs generated by the Star 2‐Process
Author(s) -
Robalewska Hanna
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199709)11:2<125::aid-rsa3>3.0.co;2-u
Subject(s) - random graph , star (game theory) , struct , random regular graph , poisson distribution , mathematics , poisson process , combinatorics , discrete mathematics , graph , degree (music) , computer science , 1 planar graph , statistics , chordal graph , physics , mathematical analysis , acoustics , programming language
The star 2‐process “greedily” generates graphs with maximum degree 2 in a natural way. We can obtain information about the final graph of this process; for instance, that is almost surely 2‐regular. We also find the probability of hamiltonicity and Poisson approximations of the distributions of numbers of cycles and short cycles. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 125–149 (1997)