The asymptotic number of claw-free cubic graphs

Brendan D. McKay; Edgar M. Palmer; Ronald C. Read; Robert W. Robinson

doi:10.1016/S0012-365X(03)00188-2

The asymptotic number of claw-free cubic graphs

Brendan D. McKay^*, Edgar M. Palmer, Ronald C. Read, Robert W. Robinson

^*Corresponding author for this work

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

4 Citations (Scopus)

Abstract

Let H_n be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for H_n. Here we determine the asymptotic behavior of this sequence: H_n ∼ (2n)!/e√6πn (n/2e) ^n/3 e^(n/2)(1/3). We have verified this formula using known asymptotic estimates of cubic graphs with loops and multiple edges and also by the method of inclusion and exclusion.

Original language	English
Pages (from-to)	107-118
Number of pages	12
Journal	Discrete Mathematics
Volume	272
Issue number	1
DOIs	https://doi.org/10.1016/S0012-365X(03)00188-2
Publication status	Published - 28 Oct 2003

Access to Document

10.1016/S0012-365X(03)00188-2

Cite this

@article{93b1a7d3cc9d4c11870f1bc51650ae2e,

title = "The asymptotic number of claw-free cubic graphs",

abstract = "Let Hn be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for Hn. Here we determine the asymptotic behavior of this sequence: Hn ∼ (2n)!/e√6πn (n/2e) n/3 e(n/2)(1/3). We have verified this formula using known asymptotic estimates of cubic graphs with loops and multiple edges and also by the method of inclusion and exclusion.",

keywords = "Asymptotic enumeration, Claw-free, Cubic graphs",

author = "McKay, {Brendan D.} and Palmer, {Edgar M.} and Read, {Ronald C.} and Robinson, {Robert W.}",

year = "2003",

month = oct,

day = "28",

doi = "10.1016/S0012-365X(03)00188-2",

language = "English",

volume = "272",

pages = "107--118",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - The asymptotic number of claw-free cubic graphs

AU - McKay, Brendan D.

AU - Palmer, Edgar M.

AU - Read, Ronald C.

AU - Robinson, Robert W.

PY - 2003/10/28

Y1 - 2003/10/28

N2 - Let Hn be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for Hn. Here we determine the asymptotic behavior of this sequence: Hn ∼ (2n)!/e√6πn (n/2e) n/3 e(n/2)(1/3). We have verified this formula using known asymptotic estimates of cubic graphs with loops and multiple edges and also by the method of inclusion and exclusion.

AB - Let Hn be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for Hn. Here we determine the asymptotic behavior of this sequence: Hn ∼ (2n)!/e√6πn (n/2e) n/3 e(n/2)(1/3). We have verified this formula using known asymptotic estimates of cubic graphs with loops and multiple edges and also by the method of inclusion and exclusion.

KW - Asymptotic enumeration

KW - Claw-free

KW - Cubic graphs

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

U2 - 10.1016/S0012-365X(03)00188-2

DO - 10.1016/S0012-365X(03)00188-2

M3 - Article

SN - 0012-365X

VL - 272

SP - 107

EP - 118

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

The asymptotic number of claw-free cubic graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this