Cuts leaving components of given minimum order (Q1773356): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1016/j.disc.2004.11.004 / rank | |||
Property / DOI | |||
Property / DOI: 10.1016/J.DISC.2004.11.004 / rank | |||
Normal rank |
Latest revision as of 10:25, 11 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cuts leaving components of given minimum order |
scientific article |
Statements
Cuts leaving components of given minimum order (English)
0 references
28 April 2005
0 references
For a connected graph \(G\) the restricted edge-connectiv\-ity \(\lambda_2(G)\) is defined as the minimum cardinality of an edge-cut over all edge-cuts \(S\) such that each component of \(G-S\) contains at least \(p\) vertices. The authors introduce a generalization \(\lambda^q_p(G)\) defined as the minimum cardinality such that one component of \(G-S\) contains at least \(p\) vertices and another component contains at least \(q\) vertices \((p,q>0)\). Analogously \(K^q_p(G)\) for vertex-connectiv\-ity is introduced. They prove that \(K^p_1(G)\leq \lambda^p_p(G)\), which can be seen as a generalization of Whitneys well-known inequality \(K(G)\leq \lambda(G)\).
0 references
edge-cut
0 references
vertex-cut
0 references
restricted edge-connectivity
0 references
restricted vertex-connectivity
0 references
0 references