Short cycles in random regular graphs

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

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    75 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
    DOIs
    Publication statusPublished - 20 Sept 2004

    Fingerprint

    Dive into the research topics of 'Short cycles in random regular graphs'. Together they form a unique fingerprint.

    Cite this