Ginsburg and Sands defined a procedure for completely disconnecting graphs: each round, remove at most one edge from each component and at most w edges total. Define f_w(g) to be the minimal number of rounds to reduce G to isolated vertices. Prior work of Ginsburg and Sands has determined f_w(P_n) for 2 ≤ w ≤ ∞ and the lead-term asymptotics of f_∞(K_n) and f_2(K_n)). We show that when T is a tree with e edges and max degree at most Δ, f_∞(T) ≤ log Δ/(Δ-1) (e - Δ) + Δ. We also give sharp bounds for some specific families of trees.
展开▼
