Short cycles in random regular graphs

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

doi:10.37236/1819

Short cycles in random regular graphs

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

79 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 language	English
Pages (from-to)	1-12
Number of pages	12
Journal	Electronic Journal of Combinatorics
Volume	11
Issue number	1 R
DOIs	https://doi.org/10.37236/1819
Publication status	Published - 20 Sept 2004

Access to Document

10.37236/1819

Cite this

@article{c88501b6f420485ebf1cebcaa48725db,

title = "Short cycles in random regular graphs",

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.",

author = "McKay, {Brendan D.} and Wormald, {Nicholas C.} and Beata Wysocka",

year = "2004",

month = sep,

day = "20",

doi = "10.37236/1819",

language = "English",

volume = "11",

pages = "1--12",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1 R",

}

TY - JOUR

T1 - Short cycles in random regular graphs

AU - McKay, Brendan D.

AU - Wormald, Nicholas C.

AU - Wysocka, Beata

PY - 2004/9/20

Y1 - 2004/9/20

N2 - 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.

AB - 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.

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

U2 - 10.37236/1819

DO - 10.37236/1819

M3 - Article

SN - 1077-8926

VL - 11

SP - 1

EP - 12

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1 R

ER -

Short cycles in random regular graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this