CONNECTIVITY AND SEPARATING SETS OF CAGES

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 induc ed subgraph G[S] has diameter at least [g/2],with equality only when d istance [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 gre ater than or equal to 3 is 3-connected. This result supports the conje cture 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 tha t G - V(C) is connected. We prove that every (k; g)-cage contains a no nseparating g-cycle. For even g, we prove that every g-cycle in a (k; g)-cage is nonseparating. (C) 1998 John Wiley & Sons, Inc.