- Tytuł:
- A Sufficient Condition for Graphs to Be Super k-Restricted Edge Connected
- Autorzy:
-
Wang, Shiying
Wang, Meiyu
Zhang, Lei - Powiązania:
- https://bibliotekanauki.pl/articles/31341790.pdf
- Data publikacji:
- 2017-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph
neighborhood
k -restricted edge connectivity
super k -restricted edge connected graph - Opis:
- 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 $ \lambda_k (G) $, is defined as the cardinality of a minimum $k$-restricted edge cut. Let \( \xi_k(G) = \text{min} \{ | [ X , \overline{X} ] | : |X| = k, G[X] \) is connected $ \} $, where $ \overline{X} = V (G) \backslash 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 $ \nu \ge 2k$. In this paper, we show that if $ | N( u ) \cup N( v ) | \ge k +1 $ for all pairs $u$, $v$ of nonadjacent vertices and $ \xi_k (G) \le \floor{ ν/2}+k $, then $G$ is super $k$-restricted edge connected.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 537-545
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł