Extremal graphs with given order and the rupture degree

Yinkui Li, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 languageEnglish
Pages (from-to)1706-1710
Number of pages5
JournalComputers and Mathematics with Applications
Volume60
Issue number6
DOIs
StatePublished - 2010

Keywords

  • Extremal graphs
  • Nonlinear integer programming
  • The rupture degree

Fingerprint

Dive into the research topics of 'Extremal graphs with given order and the rupture degree'. Together they form a unique fingerprint.

Cite this