Back to Search
Start Over
Cuts leaving components of given minimum order
- Source :
-
Discrete Mathematics . Mar2005, Vol. 292 Issue 1-3, p55-65. 11p. - Publication Year :
- 2005
-
Abstract
- 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]
- Subjects :
- *PAPER
*EQUALITY
*POLITICAL science
*DEMOCRACY
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 292
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 17613381
- Full Text :
- https://doi.org/10.1016/j.disc.2004.11.004