Sufficient conditions for λ′-optimality of graphs with small conditional diameter

A restricted edge-cut S of a connected graph G is an edge-cut such that G - S has no isolated vertex. The restricted edge-connectivity lambda'(G) is the minimum cardinality over all restricted edge-cuts. A graph is said to lambda'-optimal if lambda'(G) = xi(G), where xi(G) denotes the minimum edge-degree of G defined as xi(G) = min{d(u) + d(nu) - 2: u nu is an element of E(G)}. The P-diameter of G measures how far apart a pair of subgraphs satisfying a given property P can be, and hence it generalizes the standard concept of diameter. In this paper we prove two kind of results, according to which property P is chosen. First, let D-1 (resp. D-2) be the P-diameter where P is the property that the corresponding subgraphs have minimum degree at least one (resp. two). We prove that a graph with odd girth g is lambda'-optimal if D-1 <= g - 2 and D-2 <= g - 5. For even girth we obtain a similar result. Second, let F subset of V(G) with vertical bar F vertical bar = delta - 1, delta >= 2, being the minimum degree of G. Using the property Q of being vertices of G - F we prove that a graph with girth g is not an element of {4, 6, 8} is lambda'-optimal if this Q-diameter is at most 2[(g - 3)/2]. (c) 2005 Elsevier B.V. All rights reserved.