Rupture degree of graphs

Abstract

We introduce a new graph parameter, the rupture degree. The rupture degree for a complete graph K _n is defined as 1−n, and the rupture degree for an incomplete connected graph G 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 used to measure the vulnerability of networks. Rupture degrees of several specific classes of graphs are determined. Formulas for the rupture degree of join graphs and some bounds of the rupture degree are given. We also obtain some Nordhaus–Gaddum type results for the rupture degree.

Keywords:

• Network vulnerability
• Rupture degree
• Nordhaus–Gaddum type result

Acknowledgements

This work was supported by NSFC (No. 10101021), S&T Innovative Foundation for Young Teachers and DPOP in NPU.