On \((t, K)\)-Shredders in \(k\)-Connected Graphs

Zeev Nutov1, Masao Tsugaki2
1Department of Computer Science The Open University of Israel
2Department of Mathematical Information Science Science University of Tokyo

Abstract

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