The rupture degree of trees.

For the complete graph Kn, its rupture degree is defined as 1-n; and for a noncomplete connected graph G, its rupture degree is defined by r(G)=max{ω(G - X)-|X|-m(G - X):X ⊂ V(G), ω(G - X) > 1 }, where ω(G - X) is the number of components of G - X and m(G - X) is the order of a largest component of G - X. It is shown that this parameter can be well used to measure the vulnerability of networks. Li and Li proved in 2004 that computing the rupture degree for a general graph is NP-complete. In this paper, we give a recursive algorithm for computing the rupture degree of trees, and determine the maximum and minimum rupture degree of trees with given order and maximum degree. [ABSTRACT FROM AUTHOR]