The asymptotic distribution of short cycles in random regular graphs

Research output: Contribution to journalArticleResearchpeer-review

90 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)168-182
Number of pages15
JournalJournal of Combinatorial Theory, Series B
Volume31
Issue number2
DOIs
Publication statusPublished - 1981
Externally publishedYes

Cite this