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

Abstract

Let $G=(V,E)$ be a $k$-connected graph. For $t\ge 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\le 2t–3$.