Minimally restricted edge connected graphs

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

来源：Applied Mathematics Letters, 2008, 21(8): 820-823.

DOI：10.1016/j.aml.2007.09.004

• restricted edge connectivity

For a connected graph G = (V, E), an edge set S subset of E is a restricted edge cut if G - S is disconnected and there is no isolated vertex in G - S. The cardinality of a minimum restricted edge cut of G is the restricted edge connectivity of G, denoted by lambda';(G). A graph G is called minimally restricted edge connected if lambda';(G - e) < lambda';(G) for each edge e is an element of E. A graph G is lambda';-optimal if lambda';(G) = xi(G), where xi(G) is the minimum edge degree of G. We show in this work that a minimally restricted edge connected graph is always lambda';-optimal.

• 出版日期2008-8
• 单位新疆大学