Lower connectivities of regular graphs with small diameter

Krishnamoorthy et al. [Minimum order graphs with specified diameter, connectivity and regularity, Networks 19 (1989) 25–46.] showed that a δδ-regular graph with diameter D   at most 3 has (vertex-)connectivity κκ at least 2, and if D⩽2D⩽2 then the connectivity is at least κ⩾min{δ,3}κ⩾min{δ,3}. Likewise, Soneoka et al [Sufficient conditions for maximally connected dense graphs, Discrete Math. 63 (1) (1987) 53–66] proved that a graph with diameter D⩽2⌊(g-1)/2⌋-1D⩽2⌊(g-1)/2⌋-1 has maximum connectivity κ=δκ=δ. In this work we generalize and improve these results for δδ-regular graphs. More precisely we prove that if D⩽2⌊(g-1)/2⌋+1D⩽2⌊(g-1)/2⌋+1 then κ⩾2κ⩾2, and if D⩽g-1D⩽g-1 then κ⩾min{δ,3}κ⩾min{δ,3}. Furthermore, we prove for g   even that if D⩽g-2D⩽g-2 then κ⩾min{δ,6}κ⩾min{δ,6}, and for bipartite δδ-regular graphs we obtain that if D⩽g-1D⩽g-1 then κ⩾min{δ,4}κ⩾min{δ,4}, and if D⩽gD⩽g then κ⩾2κ⩾2. We establish similar bounds for the edge connectivity and present some examples showing that these results are best possible, at least for particular values of the girth and the regularity δδ.