Cuts leaving components of given minimum order (Q1773356): Difference between revisions

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)\).