Neighbor Rupture Degree of Graphs

The vulnerability shows the endurance of the network until the communication collapse after the breakdown of certain stations or communication links. If a spy or a station is invaded in a spy network, then the adjacent stations are treacherous. A vulnerability parameter the neighbor rupture degree can be used to obtain the vulnerability of a spy network. The neighbor rupture degree of a noncomplete connected graph G is defined to be Nr(G) = max{w(G/S) − |S| − c(G/S) : S ⊂ V (G), w(G/S) ≥ 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 thesis, the neighbor rupture degree of Harary graphs which are the maximum possible connectivity with the minimum number of edges are obtained.