TY - JOUR

T1 - The asymptotic distribution of short cycles in random regular graphs

AU - Wormald, Nicholas C.

PY - 1981

Y1 - 1981

N2 - The probability that a random labelled r-regular graph contains a given number of cycles of given length is investigated asymptotically. Cycles of a finite number of different fixed lengths can be handled simultaneously. For i≠j, the probabilities of an i-cycle and a j-cycle occurring are asymptotically independent. The results are actually derived in the more general setting of graphs which have any given degree sequence, as long as the maximum degree is bounded above by a constant. As a special case, an asymptotic formula results for the number of labelled r-regular graphs with a given girth.

AB - The probability that a random labelled r-regular graph contains a given number of cycles of given length is investigated asymptotically. Cycles of a finite number of different fixed lengths can be handled simultaneously. For i≠j, the probabilities of an i-cycle and a j-cycle occurring are asymptotically independent. The results are actually derived in the more general setting of graphs which have any given degree sequence, as long as the maximum degree is bounded above by a constant. As a special case, an asymptotic formula results for the number of labelled r-regular graphs with a given girth.

UR - http://www.scopus.com/inward/record.url?scp=0010746686&partnerID=8YFLogxK

U2 - 10.1016/S0095-8956(81)80022-6

DO - 10.1016/S0095-8956(81)80022-6

M3 - Article

AN - SCOPUS:0010746686

VL - 31

SP - 168

EP - 182

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

IS - 2

ER -