Connectivity of Cages/1997

Originator(s): H. L. Fu, K. C. Huang, and C. A. Rodger (Auburn Univ.)

Definitions: A (k,g)-cage is a graph with minimum number of vertices among the k-regular graphs with girth g. Erdos and Sachs [ES] showed the existence of cages for k,g\ge2.

Conjecture/Question: Every (k,g)-cage is k-connected.

Comments/Partial results: Fu-Huang-Rodger [FHR] proved the conjecture for k=3. Jiang-Mubayi [JM] and Daven-Rodger [DR] independently proved that all cages with k\ge3 are 3-connected. Pelayo-Marcote-Balbuena [PMB] showed that 3-regular cages with girth at least 5 are quasi-4-connected.

In the study of connectivity, a graph is said to be maximally connected if its connectivity equals its minimum degree. It is superconnected if it is maximally connected and every minimum cutset is trivial (a vertex neighborhood). A 3-regular graph is quasi-4-connected if it is superconnected and deletion of any minimum cutset leaves only two components.

References: [DR] M. Daven and C.A. Rodger, (k, g)-cages are 3- connected, Discrete Math. 199 (1999), 207215.
[ES] P. Erdos and H. Sachs, Regulare Graphen gegebener Taillen- weite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963), 251257.
[FHR] H.L. Fu, K.C. Huang and C.A. Rodger, Connectivity of Cages, J. Graph Theory 24 (1997), 187191.
[JM] T. Jiang and D. Mubayi, Connectivity and Separating Sets of Cages, J. Graph Theory 29 (1998), 3544.
[PMB] I. Pelayo, X. Marcote, and C. Balbuena, Every cubic cage is quasi-4-connected.

Index Page; Glossary


Posted 06/12/05; Last update 06/12/05