Connectivity and separating sets of cages
Tao Jiang, Dhruv Mubayi · Journal of Graph Theory · 1998
A (k; g)-cage is a graph of minimum order among k-regular graphs with girth g. We show that for every cutset S of a (k; g)-cage G, the induced subgraph G[S] has diameter at least ⌊g/2⌋, with equality only when distance ⌊g/2⌋ occurs for at least two pairs of vertices in G[S]. This structural property is used to prove that every (k; g)-cage with k ≥ 3 is 3-connected. This result supports the conjecture of Fu, Huang, and Rodger that every (k; g)-cage is k-connected. A nonseparating g-cycle C in a graph G is a cycle of length g such that G − V(C) is connected. We prove that every (k; g)-cage contains a nonseparating g-cycle. For even g, we prove that every g-cycle in a (k; g)-cage is nonseparating. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 35–44, 1998