Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 1706-1710 |
Number of pages | 5 |
Journal | Computers and Mathematics with Applications |
Volume | 60 |
Issue number | 6 |
DOIs | |
State | Published - 2010 |
Keywords
- Extremal graphs
- Nonlinear integer programming
- The rupture degree