Extremal graphs with given order and the rupture degree

The rupture degree of an incomplete connected graph G is defined by r(G)=maxω(G-X)-|X|-τ(G-X):X⊂V(G),ω(G-X)>1, where ω(G-X) is the number of components of G-X and τ(G-X) is the order of a largest component of G-X. In Li and Li [5] and Li et al. (2005) [4], it was shown that the rupture degree can be well used to measure the vulnerability of networks. In this paper, the maximum and minimum networks with prescribed order and the rupture degree are obtained. Finally, we determine the maximum rupture degree graphs with given order and size.