The rupture degree of trees

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:

• rupture degree
• recursive algorithm
• tree

CCS Category:

• C.2.0
• G.2.2