Sufficient conditions for lambda '-optirnality in graphs with girth g

摘要

For a connected graph the restricted edge-connectivity lambda'(G) is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that there are no isolated vertices in G - S. A graph G is said to be lambda'-optimal if lambda'(G) = xi(G), where xi(G) is the minimum edge-degree in G defined as xi(G) = min{d(u) + d(v) - 2:uv is an element of E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for lambda'-optimality in graphs of diameter 2, Discrete Math 283 (2004), 113-120] gave a sufficient condition for lambda'-optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g - 1, g being the girth of the graph, and show that a graph G with diameter at most g - 2 is lambda'-optimal. (c) 2006 Wiley Periodicals, Inc.