Extraconnectivity of \(s\)-geodetic digraphs and graphs
The \(\eta\)-extraconnectivity \(\kappa _\eta\) of a (di)graph \(G\) is the minimum cardinality of a set of vertices whose deletion disconnects \(G\) in such a way that all remaining (strongly) connected components have cardinality greater than \(\eta\). A (di)graph \(G\) with diameter \(D>1\) is said to be \(s\)-geodetic, \(1\leq s\leq D\), if for any two of its vertices \(x\) and \(y\) there exists at most one \(x\)-\(y\) path of length not exceeding \(s\). Starting from results of the paper by \textit{C. Balbuena, A. Carmona, J. Fábrega} and \textit{M. A. Fiol} [Discrete Math. 167/168, 85-100 (1997; Zbl 0874.05033)] sufficient conditions are given to assure the maximum \(\eta\)-extraconnectivity of such a digraph with minimum degree \(\delta\). Similar conditions are given for \(s\)-geodetic digraphs. The corresponding edge versions of these results are also discussed.
scientific article; zbMATH DE number 1320575
scientific article