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

Camino Balbuena

Universitat Politècnica de Catalunya

A ($\delta$,$g$)-cage is a $\delta$-regular graph with girth $g$ and with the least possible number of vertices. It has been proved that every $(\delta;g)$-cage with $\delta\ge 3$ is 3-connected [See the papers by M. Daven and C. A. Rodger, $(k;g)$-cages are $3$-connected, Discrete Math. 199 (1999), 207-215; or the paper by T. Jiang and D. Mubayi, Connectivity and separating sets of cages, Journal of Graph Theory 29 (1998), 35-44].

In this work we prove that all ($\delta$,$g$)-cages are $r$-connected with $r\ge\sqrt{\delta+1}$ for $g\ge 7$ odd. This result supports the conjecture of Fu, Huang and Rodger that all $(\delta;g)$-cages are $\delta$-connected.