Generation of cubic graphs

Gunnar Brinkmann; Jan Goedgebeur; Brendan D. McKay

Generation of cubic graphs

Gunnar Brinkmann^*
, Jan Goedgebeur
, Brendan D. McKay

^*Corresponding author for this work

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

50 Citations (Scopus)

Abstract

We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.

Original language	English
Pages (from-to)	69-80
Number of pages	12
Journal	Discrete Mathematics and Theoretical Computer Science
Volume	13
Issue number	2
Publication status	Published - 2011

Cite this

@article{f2433f7735734140a5ebda52783639ec,

title = "Generation of cubic graphs",

abstract = "We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.",

keywords = "Canonical construction path, Cubic graph, Generation, Graph",

author = "Gunnar Brinkmann and Jan Goedgebeur and McKay, \{Brendan D.\}",

year = "2011",

language = "English",

volume = "13",

pages = "69--80",

journal = "Discrete Mathematics and Theoretical Computer Science",

issn = "1462-7264",

publisher = "Maison de l'informatique et des mathematiques discretes",

number = "2",

}

TY - JOUR

T1 - Generation of cubic graphs

AU - Brinkmann, Gunnar

AU - Goedgebeur, Jan

AU - McKay, Brendan D.

PY - 2011

Y1 - 2011

N2 - We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.

AB - We describe a new algorithm for the efficient generation of all non-isomorphic connected cubic graphs. Our implementation of this algorithm is more than 4 times faster than previous generators. The generation can also be efficiently restricted to cubic graphs with girth at least 4 or 5.

KW - Canonical construction path

KW - Cubic graph

KW - Generation

KW - Graph

UR - https://www.scopus.com/pages/publications/79960229377

M3 - Article

SN - 1462-7264

VL - 13

SP - 69

EP - 80

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

IS - 2

ER -

Generation of cubic graphs

Abstract

Other files and links

Fingerprint

Cite this