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.
Keywords: