Neighbor Rupture Degree and the Relations between Other Parameters

Abstract

The vulnerability shows the resistance of the network until communication breakdown after the disruption of certain stations or communication links. This study introduces a new vulnerability parameter, neighbor rupture degree. The neighbor rupture degree of a non-complete connected graph $G$ is defined to be

$$Nr(G)=max\{w(G/S)–|S|–c(G/S):S\subset V(G),w(G/S)\ge 1\}$$

where $S$ is any vertex subversion strategy of $G$, $w(G/S)$ is the number of connected components in $G/S$, and $c(G/S)$ is the maximum order of the components of $G/S$. In this paper, the neighbor rupture degree of some classes of graphs are obtained and the relations between neighbor rupture degree and other parameters are determined.