Improved lower bound for the vertex-connectivity of -cages

Camino Balbuena

Universitat Politècnica de Catalunya

A (,)-cage is a -regular graph with girth and with the least possible number of vertices. It has been proved that every -cage with is 3-connected [See the papers by M. Daven and C. A. Rodger, -cages are -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 (,)-cages are -connected with for odd. This result supports the conjecture of Fu, Huang and Rodger that all -cages are -connected.

2005-05-23