The k-Restricted Edge Connectivity of Balanced Bipartite Graphs |
| |
Authors: | Jun Yuan Aixia Liu |
| |
Institution: | 1. School of Applied Science, Taiyuan University of Science and Technology, Taiyuan, 030024, People??s Republic of China
|
| |
Abstract: | For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains 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. For two disjoint vertex sets U1,U2 ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U
1 and the other in U
2 by U
1, U
2]. Define xk(G)=min{|U,V(G)\ U]|: U{\xi_k(G)=\min\{|U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ
k
-optimal if λ
k
(G) = ξ
k
(G). A graph is said to be super-λ
k
if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ
k
-optimal or super-λ
k
. Moreover, we demonstrate that our results are best possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|