Computational determination of (3,11) and (4,7) cages

DOI10.1016/J.JDA.2010.11.001MaRDI QIDQ553952zbMATH OpenOpenAlexFDO

Authors Geoffrey Exoo, Brendan D. McKay, Jacqueline Nadon, Wendy Myrvold

Publication date 29 July 2011

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.3608

zbMATH Keywords

girthregular graphcage

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: A (k,g)-graph is a k-regular graph of girth g, and a (k,g)-cage is a (k,g)-graph of minimum order. We show that a (3,11)-graph of order 112 found by Balaban in 1973 is minimal and unique. We also show that the order of a (4,7)-cage is 67 and find one example. Finally, we improve the lower bounds on the orders of (3,13)-cages and (3,14)-cages to 202 and 260, respectively. The methods used were a combination of heuristic hill-climbing and an innovative backtrack search.

Recommendations

• New upper bounds on the order of cages
• Dynamic cage survey
• scientific article; zbMATH DE number 1303556
• On some properties of cages
• The Smallest Cubic Graphs of Girth Nine

Cites work

• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• scientific article; zbMATH DE number 1303556 (Why is no real title available?)
• scientific article; zbMATH DE number 3414342 (Why is no real title available?)
• Dynamic cage survey
• The Smallest Cubic Graphs of Girth Nine

Cited in

(9)

• Codes for distributed storage from 3-regular graphs
• scientific article; zbMATH DE number 2037806 (Why is no real title available?)
• Maximizing algebraic connectivity for certain families of graphs
• On decreasing the orders of \((k,g)\)-graphs
• scientific article; zbMATH DE number 7380482 (Why is no real title available?)
• Applications of integer programming methods to cages
• Attainable bounds for algebraic connectivity and maximally connected regular graphs
• A note on the problem of finding a (3,9)-cage
• The 10-cages and derived configurations

This page was built for publication: Computational determination of (3,11) and (4,7) cages

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