Computing the Rupture Degree in Composite Graphs

Abstract

The rupture degree of an incomplete connected graph G is defined by r (G) = max {w (G - S) - vertical bar S vertical bar - m (G - S) : S subset of 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 K(n); 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.