| Abstract: | For the complete graph K n , 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. |
