Improved lower bound for the vertex connectivity of ( ;g)-cages

DOI10.1016/J.DISC.2004.07.024MaRDI QIDQ2568484zbMATH OpenOpenAlexFDO

Authors Mirka Miller, Yuqing Lin, C. Balbuena

Publication date 10 October 2005

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2004.07.024

Mathematics Subject Classification ID

Connectivity (05C40)

Review text

A \((\delta,g)\)-cage is a \(\delta\)-regular graph with girth \(g\) and with the minimum possible number of vertices. \textit{H. L. Fu}, \textit{K. C. Huang} and \textit{C. A. Rodger} [J. Graph Theory 24, 187--191 (1997; Zbl 0866.05035)] conjectured that all \((\delta,g)\)-cages are \(\delta\)-connected. Here the authors prove that all \((\delta,0)\)-cages are \(r\)-connected with \(r\geq\sqrt{\delta+1}\) for \(g\geq 7\) odd.

Recommendations

• On the lower bound of vertex connectivity of semiregular cages
• A new bound for the connectivity of cages
• G-graphs for the cage problem: a new upper bound
• Lower bounds on the vertex-connectivity of digraphs and graphs
• Improved lower bounds for the orders of even girth cages
• On the connectivity of \((k,g)\)-cages of even girth
• On upper bounds and connectivity of cages
• On upper bounds and connectivity of cages
• Lower-bounds on the connectivities of a graph
• scientific article; zbMATH DE number 1263999

Cites work

• (\(\delta ,g\))-cages with \(g\geqslant 10\) are 4-connected
• \((k,g)\)-cages are 3-connected
• A note on the edge-connectivity of cages
• All (k;g)‐cages are edge‐superconnected
• Cages—a survey
• Connectivity of cages
• Edge-superconnectivity of cages
• Every cubic cage is quasi 4-connected
• scientific article; zbMATH DE number 4162905 (Why is no real title available?)
• scientific article; zbMATH DE number 1286481 (Why is no real title available?)
• scientific article; zbMATH DE number 2188443 (Why is no real title available?)
• scientific article; zbMATH DE number 961975 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• Maximally connected digraphs
• On the connectivity of cages with girth five, six and eight
• On the order and size of s-geodetic digraphs with given connectivity
• Sufficient conditions for maximally connected dense graphs

Cited in

(14)

• On the number of components of \((k,g)\)-cages after vertex deletion
• On superconnectivity of (4, g)-cages
• (\(\delta ,g\))-cages with \(g\geqslant 10\) are 4-connected
• New results on connectivity of cages
• Diameter and connectivity of (D; g)-cages
• On the connectivity of semiregular cages
• On superconnectivity of (4,g)-cages with even girth
• Edge-superconnectivity of semiregular cages with odd girth
• On the lower bound of vertex connectivity of semiregular cages
• A lower bound on the order of regular graphs with given girth pair
• New improvements on connectivity of cages
• Monotonicity of the order of \((D;g)\)-cages
• A new bound for the connectivity of cages
• On the connectivity of \((k,g)\)-cages of even girth

This page was built for publication: Improved lower bound for the vertex connectivity of \((\delta ;g)\)-cages

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