Sufficient conditions for super \(k\)-restricted edge connectivity in graphs of diameter 2
For a connected graph \(G=(V,E)\), a subset \(S\subseteq E\) is a \(k\)-restricted edge cut if \(G-S\) is disconnected and every component of \(G-S\) has at least \(k\) vertices. The \(k\)-restricted edge connectivity of \(G\), denoted by \(\lambda_k(G)\), is defined as the cardinality of a minimum \(k\)-restricted edge cut. Let \(\xi_k(G)=\min\{|[X,\overline X]|: |X|=k, G[X]\text{ is connected}\}\). \(G\) is \(\lambda_k\)-optimal if \(\lambda_k(G) = \xi_k(G)\). Moreover, \(G\) is super-\(\lambda_k\) if every minimum \(k\)-restricted edge cut of \(G\) isolates one connected subgraph of order \(k\). In this paper, the authors prove that if \(|N_G(u)\cap N_G(v)| \geq 2k-1\) for all pairs \(u,v\) of nonadjacent vertices, then \(G\) is \(\lambda_k\)-optimal; and if \(|N_G(u)\cap N_G(v)| \geq 2k\) for all pairs \(u, v\) of nonadjacent vertices, then \(G\) is either super-\(\lambda_k\) or in a special class of graphs.
scientific article; zbMATH DE number 5542385