On the number of shredders
Tibor Jord�n · Journal of Graph Theory · 1999
A subset S of k vertices in a k-connected graph G is a shredder, if G − S has at least three components. We show that if G has n vertices, then the number of shredders is at most n, which was conjectured by Cheriyan and Thurimella [Cheriyan & Thurimella, Proc 28th Ann ACM Symp, 1996]. If G contains no meshing shredders (in particular, if k ≤ 3), the sharp upper bound ⌊ (n − k − 1)/2⌋ is proven. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 195-200, 1999