Cuts leaving components of given minimum order Original Research Article

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