Neighbor Toughness of Graphs

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 toughness. The neighbor toughness of a graph G is defined as NT(G) = minf jSj !(G=S) : !(G=S) > 1g, where S is any vertex subversion strategy of G and !(G=S) is the number of connected components in the graph G=S. In this paper, the relations between neighbor toughness and other parameters are determined and the neighbor toughness of some specific graphs are obtained.