Cuts leaving components of given minimum order

Abstract: For a connected graph G, the restricted edge-connectivity is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that each component of contains at least p vertices. In the present paper we introduce the more general parameter defined as the minimum cardinality of an edge-cut over all edge-cuts S such that one component of contains at least p vertices and another component of contains at least q vertices where p and q are positive integers. Analogously, we define as the minimum cardinality of a vertex-cut over all vertex-cuts such that one component of contains at least p vertices and another component of contains at least q vertices. A connected graph G is -connected (-connected), if () is well-defined. First we give useful equivalences to -connectivity and -connectivity and characterize the classes of graphs which are -connected and -connected. Then we prove which generalizes Whitney''s well-known inequality . Finally, we characterize the class of graphs for which is minimum, i.e. and the class of graphs for which is maximum, i.e. or . [Copyright &y& Elsevier]