Premium
The asymptotic distribution of long cycles in random regular graphs
Author(s) -
Garmo Hans
Publication year - 1999
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(199908)15:1<43::aid-rsa3>3.0.co;2-s
Subject(s) - mathematics , combinatorics , asymptotic distribution , random regular graph , poisson distribution , random graph , limit (mathematics) , struct , limiting , distribution (mathematics) , distribution function , graph , discrete mathematics , statistics , mathematical analysis , physics , quantum mechanics , line graph , 1 planar graph , estimator , computer science , programming language , mechanical engineering , engineering
The asymptotic distribution of the number of cycles of length l in a random r ‐regular graph is determined. The length of the cycles is defined as a function of the number of vertices n , thus l = l ( n ), and the length satisfies l ( n )→∞ as n →∞. The limiting distribution turns out to depend on whether l ( n )/ n →0 or l ( n )/ n → q , 0< q <1 as n →∞. In the first case the limit distribution is a weighted sum of Poisson variables while in the other case the limit distribution is similar to the limit distribution of Hamiltonian cycles in a random r ‐regular graph. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15: 43–92, 1999