Minimally 3-restricted edge connected graphs

作者：Liu Qinghai; Hong Yanmei; Zhang Zhao^*

来源：Discrete Applied Mathematics, 2009, 157(4): 685-690.

DOI：10.1016/j.dam.2008.07.009

• Fault tolerance
• Restricted edge connectivity

For a connected graph G = (V, E), an edge set S subset of E is a 3-restricted edge Cut if G - S is disconnected and every component of G - S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by lambda(3)(G). A graph G is called minimally 3-restricted edge connected if lambda(3) (G - e) < lambda(3) (G) for each edge e is an element of E. A graph G is lambda(3)-optimal if lambda(3)(G) = xi(3)(G), where xi(3)(G) = max{omega(U) : U subset of V(G). G|U| is connected, |U| = 3}, omega(U) is the number of edges between U and V\U, and G|U| is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always lambda(3)-optimal except the 3-cube.

• 出版日期2009-2-28
• 单位新疆大学