Article ID Journal Published Year Pages File Type
4651253 Discrete Mathematics 2007 6 Pages PDF
Abstract
For a connected graph G=(V,E), an edge set S⊂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 λk(G), is defined as the cardinality of a minimum k-restricted-edge-cut. The k-isoperimetric-edge-connectivity is defined as γk(G)=min{|[U,U¯]|:U⊂V,|U|⩾k,|U¯|⩾k}, where [U,U¯] is the set of edges with one end in U and the other end in U¯=V⧹U. In this note, we give some degree conditions for a graph to have optimal λk and/or γk.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,