| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421134 | Discrete Applied Mathematics | 2015 | 6 Pages |
For a connected graph G=(V,E)G=(V,E), an edge set S⊆E(G)S⊆E(G) is called a kk-restricted edge cut of GG if G−SG−S is disconnected and every component of G−SG−S has at least kk vertices. The kk-restricted edge connectivity of GG, denoted by λk(G)λk(G), is defined as the cardinality of a minimum kk-restricted edge cut. For two disjoint vertex subsets X,YX,Y of GG, define [X,Y]={xy∈E(G):x∈X,y∈Y}[X,Y]={xy∈E(G):x∈X,y∈Y} and define ξk(G)=min{|[X,X¯]|:X⊆V(G),|X|=k,G[X]is connected}, where X¯=V(G)∖X. GG is λkλk-optimal if λk(G)=ξk(G)λk(G)=ξk(G). Furthermore, GG is super-λkλk if every minimum kk-restricted edge cut of GG isolates a connected subgraph with order kk. The kk-restricted edge connectivity is an important index to estimate the reliability of networks. In this paper, some degree conditions for graphs to be maximally kk-restricted edge connected and super kk-restricted edge connected are given.
