Short cycles in random regular graphs

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

Short cycles in random regular graphs

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

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

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	The Electronic Journal of Combinatorics
Volume	11
Issue number	1 R
Publication status	Published - 20 Sept 2004
Externally published	Yes

Cite this

@article{a99ba482011b491e8cc1c4494494463d,

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

language = "English",

volume = "11",

pages = "1--12",

journal = "The 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

M3 - Article

AN - SCOPUS:5344271248

SN - 1077-8926

VL - 11

SP - 1

EP - 12

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

IS - 1 R

ER -

Short cycles in random regular graphs

Abstract

Other files and links

Cite this