Generation of cubic graphs

MaRDI QIDQ5403062zbMATH OpenFDO

Authors Gunnar Brinkmann, Jan Goedgebeur, Brendan D. McKay

Publication date 25 March 2014

Full work available at URL https://arxiv.org/abs/1207.7010, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1801/0.html

zbMATH Keywords

graphcubic graphgenerationcanonical construction path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Connectivity (05C40)

Abstract: We describe an efficient new algorithm for the generation of fullerenes. Our implementation of this algorithm is more than 3.5 times faster than the previously fastest generator for fullerenes -- fullgen -- and the first program since fullgen to be useful for more than 100 vertices. We also note a programming error in fullgen that caused problems for 136 or more vertices. We tabulate the numbers of fullerenes and IPR fullerenes up to 400 vertices. We also check up to 316 vertices a conjecture of Barnette that cubic planar graphs with maximum face size 6 are hamiltonian and verify that the smallest counterexample to the spiral conjecture has 380 vertices.

Recommendations

• Fast generation of cubic graphs
• Generation of cubic graphs and snarks with large girth
• Fast generation of some classes of planar graphs
• scientific article; zbMATH DE number 3952807
• Fast generation of regular graphs and construction of cages

Cited in

(34)

• Spanning cubic graph designs
• Secure sets and their expansion in cubic graphs
• Generation of cubic graphs and snarks with large girth
• On the minimum leaf number of cubic graphs
• Enumerating Steiner triple systems
• Square Coloring Planar Graphs with Automatic Discharging
• Genetic theory for cubic graphs
• To be or not to be Yutsis: algorithms for the decision problem
• Improved asymptotic upper bounds for the minimum number of longest cycles in regular graphs
• Generation and properties of snarks
• On the smallest snarks with oddness 4 and connectivity 2
• Graphs with few Hamiltonian cycles
• Transforming phylogenetic networks: moving beyond tree space
• Graph structural properties of non-Yutsis graphs allowing fast recognition
• Generation of various classes of trivalent graphs
• Extremal cubic graphs for fault-tolerant locating domination
• Progress on fault-tolerant locating-dominating sets
• Breaking symmetries with high dimensional graph invariants and their combination
• scientific article; zbMATH DE number 4158673 (Why is no real title available?)
• snarkhunter
• Measures of edge-uncolorability of cubic graphs
• Fault-tolerant detectors for distinguishing sets in cubic graphs
• Switching 3-edge-colorings of cubic graphs
• Existence of regular nut graphs for degree at most 11
• K₂‐Hamiltonian graphs: II
• A counterexample to the pseudo 2-factor isomorphic graph conjecture
• Integer sequence discovery from small graphs
• Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
• Enumeration of Seidel matrices
• Recursive generation of IPR fullerenes
• Constructing all nonisomorphic supergraphs with isomorphism rejection
• Generation and new infinite families of \(K_2\)-hypohamiltonian graphs
• scientific article; zbMATH DE number 3952807 (Why is no real title available?)
• Improved bounds for hypo-Hamiltonian graphs

Describes a project that uses

Uses Software

• GENREG
• Buckygen
• CaGe

This page was built for publication: Generation of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5403062)