A new bound for the connectivity of cages

AbstractAn (r,g)-cage is an r-regular graph of girth g of minimum order. We prove that all (r,g)-cages are at least ⌈r/2⌉-connected for every odd girth g≥7 by means of a matrix technique which allows us to construct graphs without short cycles. This lower bound on the vertex connectivity of cages is a new advance in proving the conjecture of Fu, Huang and Rodger which states that all (r,g)-cages are r-connected