Improved lower bounds for the orders of even girth cages

MaRDI QIDQ727055zbMATH OpenFDO

Authors Tatiana Baginová Jajcayová, Slobodan Filipovski, Robert Jajcay

Publication date 6 December 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p55

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-regular graphscagesexcessgirthMoore bound

Mathematics Subject Classification ID

Graph theory (05C99)

Review text

Summary: The well-known Moore bound \(M(k,g)\) serves as a universal lower bound for the order of \(k\)-regular graphs of girth \(g\). The excess \(e\) of a \(k\)-regular graph \(G\) of girth \(g\) and order \(n\) is the difference between its order \(n\) and the corresponding Moore bound, \(e=n - M(k,g) \). We find infinite families of parameters \((k,g)\), \(g\) even, for which we show that the excess of any \(k\)-regular graph of girth \(g\) is larger than \(4\). This yields new improved lower bounds on the order of \(k\)-regular graphs of girth \(g\) of smallest possible order; the so-called \((k,g)\)-cages. We also show that the excess of the smallest \(k\)-regular graphs of girth \(g\) can be arbitrarily large for a restricted family of \((k,g)\)-graphs satisfying a very natural additional structural property.

Recommendations

• New upper bounds on the order of cages
• Counting cycles in graphs with small excess
• On the non-existence of antipodal cages of even girth
• Biregular cages of odd girth
• A lower bound on the order of regular graphs with given girth pair

Cites work

• Counting cycles in graphs with small excess
• Dynamic cage survey
• Excess in Vertex-Transitive Graphs
• Graphs with even girth and small excess
• scientific article; zbMATH DE number 1439410 (Why is no real title available?)
• scientific article; zbMATH DE number 3432305 (Why is no real title available?)
• scientific article; zbMATH DE number 3412694 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• On graphs with excess or defect 2
• On the excess of vertex-transitive graphs of given degree and girth
• On the impossibility of certain Moore graphs
• Regular graphs with excess one
• Regular Graphs with Given Girth and Restricted Circuits
• Small vertex-transitive graphs of given degree and girth
• The non-existence of certain regular graphs of girth 5

Cited in

(10)

• Edge-girth-regular graphs
• On the non-existence of antipodal cages of even girth
• On biregular bipartite graphs of small excess
• Improved lower bound for the vertex connectivity of \((\delta ;g)\)-cages
• On the order of bi-regular cages of even girth
• scientific article; zbMATH DE number 5555979 (Why is no real title available?)
• On bipartite cages of excess 4
• Counting cycles in graphs with small excess
• On a relation between bipartite biregular cages, block designs and generalized polygons
• Theoretical and computational approaches to determining sets of orders for (k, g)-graphs

This page was built for publication: Improved lower bounds for the orders of even girth cages

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