A Sufficient Condition for Graphs to Be Super K-Restricted Edge Connected - Wang Shiying; Wang Meiyu; Zhang Lei (Discussiones Mathematicae Graph Theory, 2017)
For a subset S of edges in a connected graph G, S 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 λk(G), is defined as the cardinality of a minimum k-restricted edge cut. Let ξk(G) = min{|[X, X̄]| : |X| = k, G[X] is connected}, where X̄ = V (G)\X. A graph G is super k-restricted edge connected if every minimum k-restricted edge cut of G isolates a component of order exactly k. Let k be a positive integer and let G be a graph of order ν ≥ 2k. In this paper, we show that if |N(u) ∩ N(v)| ≥ k +1 for all pairs u, v of nonadjacent vertices and ξk(G)≤⌊ν2⌋+k$ξ _k (G) \le \left\lfloor {{ν \over 2}} \right\rfloor + k$ , then G is super k-restricted edge connected.