On a kind of reliability analysis of networks

摘要

A network is often modeled by a graph G = (V, E). An edge set F ⊂ E is a 3-restricted edge cut, if G − F is disconnected and every component of G − F has at least three vertices. The 3-restricted edge connectivity λ3(G) of G is the cardinality of a minimum 3-restricted edge cut of G. A graph G is λ3-connected, if 3-restricted edge cuts exist. A graph G is called λ3-optimal, if λ3(G) = ξ3(G), whereξ3(G)=min{|[U,U¯]|:U⊂V,|U|=3andG[U]is connected}.G[U] is the subgraph of G induced by the vertex subset U  ⊆ V, and ⧹U¯=V⧹U is the complement of U·[U,U¯] is the set of edges with one end in U and the other in U¯. In this paper, we give some sufficient conditions for graphs to be λ3-optimal.