On minimally (n, lambda)-connected graphs

A graph G is (n, lambda)-connected if it satisfies the following conditions : (1) \V(G)\ greater than or equal to n + 1; (2) for any subset S subset of or equal to V(G) and any subset L subset of or equal to E(G) with lambda \ S\ + \L\ < n lambda, G - S - L is connected. The (n, lambda)-connectivity i s a common extension of both the vertex-connectivity and the edge-connectiv ity. An (n, 1)-connected graph is an n-(vertex)-connected graph, and a (1, lambda)-connected graph is a lambda-edge-connected graph. An (n, lambda)-co nnected graph G is said to be minimally (n, lambda)-connected if for any ed ge e in E(G), G - e is not (n, lambda)-connected. Let G be a minimally (n, lambda)-connected graph and let W be the set of its vertices of degree more than n lambda. Then we first prove that for any subset W' of W, the minimu m degree of the subgraph of G induced by the vertex set W' is less than or equal to lambda. This result is an extension of a theorem of Mader, which s tates that the subgraph of a minimally n-connected graph induced by the ver tices of degree more than n is a forest. By using our result, we show that if G is a minally (n, lambda)-connected graph, then (1) \E(G)\ less than or equal to lambda(\V(G)\ + n)(2)/8 for n + 1 less than or equal to \V(G) les s than or equal to 3n - 2; (2) \E(G)\ less than or equal to n lambda(\V(G)\ - n) for \V(G)\ greater than or equal to 3n - 1. Furthermore, we study the number of vertices of degree n lambda in a minimally n lambda-connected gr aph. (C) 2000 Academic Press.