Short cycles in random regular graphs

Brendan D. McKay, Nicholas C. Wormald, Beata Wysocka

Research output: Contribution to journalArticleResearchpeer-review

56 Citations (Scopus)

Abstract

Consider random regular graphs of order n and degree d = d(n) ≥ 3. Let g = g(n) ≥ 3 satisfy (d-1)2g-1 = o(n). Then the number of cycles of lengths up to g have a distribution similar to that of independent Poisson variables. In particular, we find the asymptotic probability that there are no cycles with sizes in a given set, including the probability that the girth is greater than g. A corresponding result is given for random regular bipartite graphs.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalElectronic Journal of Combinatorics
Volume11
Issue number1 R
Publication statusPublished - 20 Sep 2004
Externally publishedYes

Cite this