Let \(G = (V, E)\) be a \(k\)-connected graph. For \(t \geq 3\), a subset \(T \subset V\) is a \((t,k)\)-shredder if \(|T| = k\) and \(G – T\) has at least \(t\) connected components. It is known that the number of \((t,k)\)-shredders in a \(k\)-connected graph on \(n\) nodes is less than \(\frac{2n}{2t – 3}\). We show a slightly better bound for the case \(k \leq 2t – 3\).
Citation
Zeev Nutov, Masao Tsugaki. On \((t, K)\)-Shredders in \(k\)-Connected Graphs[J], Ars Combinatoria, Volume 083. 213-219. .