A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected

Shiying Wang, Meiyu Wang, and Lei Zhang. "A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected." Discussiones Mathematicae Graph Theory 37.3 (2017): 537-545. <http://eudml.org/doc/288354>.

@article{ShiyingWang2017,
abstract = {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). 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 $\xi _k (G) \le \left\lfloor \{\{\nu \over 2\}\} \right\rfloor + k$ , then G is super k-restricted edge connected.},
author = {Shiying Wang, Meiyu Wang, Lei Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; neighborhood; k-restricted edge connectivity; super k-restricted edge connected graph},
language = {eng},
number = {3},
pages = {537-545},
title = {A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected},
url = {http://eudml.org/doc/288354},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Shiying Wang
AU - Meiyu Wang
AU - Lei Zhang
TI - A Sufficient Condition for Graphs to Be SuperK-Restricted Edge Connected
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 537
EP - 545
AB - 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). 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 $\xi _k (G) \le \left\lfloor {{\nu \over 2}} \right\rfloor + k$ , then G is super k-restricted edge connected.
LA - eng
KW - graph; neighborhood; k-restricted edge connectivity; super k-restricted edge connected graph
UR - http://eudml.org/doc/288354
ER -