Relationships between rupture degree and other parameters

Abstract

The rupture degree of an incomplete connected graph G is defined by

where ω (G−X) denotes the number of components in the graph G−X and m(G−X) is the order of the largest component of 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, the relationships between the rupture degree and some other vulnerability parameters, namely the scattering number, toughness, integrity, and tenacity, are established. Examples show that the results are the best possible.

Keywords:

• Rupture degree
• Scattering number
• Toughness
• Integrity
• Tenacity

Acknowledgements

The authors would like to thank the anonymous referees for their constructive suggestions and critical comments which resulted in a much improved paper. The work was supported by the National Science Foundation of China under contract No. 70431001 and the China Postdoctoral Science Foundation under contract No. 2004036391.