On the extraconnectivity of graphs (Q1923481)

The authors extend their results on \(n\)-extraconnectivities \(\kappa(n)\) and \(\lambda(n)\) of a connected graph \(G\) with minimum degree \(\delta\), \(n\geq0\) (see [Discrete Math. 125, No. 1-3, 169-176 (1994; Zbl 0796.05058)] and [Discrete Math. 127, No. 1-9, 163-170 (1994; Zbl 0797.05058)]) (only minimum separators \(S\) are considered for which every component of \(G-S\) has more than \(n\) vertices). The authors establish sufficient conditions for \(G\) to attain the upper bound \((n+1)\delta-2n\) for \(\kappa(n)\) and \(\lambda(n)\). For example, if the girth \(g\) of \(G\) is odd and \(n\) is even then \(\lambda(n)\) is optimal whenever the diameter \(D\leq g-1-n\).