Computing the rupture degree in composite graphs

The rupture degree of an incomplete connected graph G is defined by r(G) = max {w (G -S) - |S|m (G - S): S ? V (G), w (G - S) > 1} where w(G - S) is the number of components of G - S and m(G - S) is the order of a largest component of G - S. For the complete graph Kn, rupture degree is defined as 1 - n. This parameter can be used to measure the vulnerability of a graph. Rupture degree can reflect the vulnerability of graphs better than or independent of the other parameters. To some extent, it represents a trade-off between the amount of work done to damage the network and how badly the network is damaged. Computing the rupture degree of a graph is NP-complete. In this paper, we give formulas for the rupture degree of composition of some special graphs and we consider the relationships between the rupture degree and other vulnerability parameters. © 2010 World Scientific Publishing Company