关键词: 图, 组合优化, 弱毁裂度, 网络抗毁性

Abstract: Weak rupture degree is an important parameter for measuring the invulnerability of networks. It combines the difficulty of destroying a network and the severity of the network being destroyed, and considers the number of edges in the remaining subgraph. In order to reveal the internal relationship between the weak rupture degree and the network structure, so as to accurately quantify networks' invulnerability, we initially give some basic properties of the weak rupture degree. Based on this, the relationship between this parameter and several important graphic parameters is studied by combinatorial optimization and analogy methods. These relationships are given in the form of the upper and lower bounds of weak rupture degree, which essentially reflect the characteristics of the network structure in the sense of the weak rupture degree, or invulnerability. These results show that weak rupture degree has obvious advantages in measuring the invulnerability of certain networks. The methods used in this paper have important guidence for network invulnerability analysis, and the obtained results have certain promotion and application value for network invulnerability design.

Key words: graph, combinatorial optimization, weak rupture degree, network invulnerability