5-Shredders in 5-Connected Graphs
by
Yoshimi Egawa
Dept of Applied Mathematics, Science University of Tokyo

For a graph G, a subset S of V(G) is called a shredder if G - S consists of three or more components. A shredder with cardinality k is referred to as a k-shredder. It is known that if G is a k-connected graph, then the number of k-shredders of G is at most (|V(G)|-k+1)/2 if 1 <= k <= 3, at most 5|V(G)|/8 if k=4, and at most (2|V(G)|-1)/3 if k >= 5. We show that if G is a 5-connected graph with sufficiently large order, then the number of 5-shredders of G is at most (2|V(G)|-10)/3.

Date received: April 18, 2001