Computing the rupture degrees of graphs

The rupture degree of a noncomplete connected graph G is defined by r(G) = max{ω(G - X) - |X| - m(G - X) : X ⊂ V(G), ω(G - X) ≥ 2}, where ω(G - X) denotes the number of components in the graph G - X. For a complete graph K_n, we define r(K_n) = 1 - n. This parameter can be used to measure the vulnerability of a graph. 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. In this paper, we prove that the problem of computing the rupture degree of a graph is NP-complete. We obtain the rupture degree of the Cartesian product of some special graphs and also give the exact values or bounds for the rupture degrees of Harary graphs.