Stability measure of a graph: A survey

Abstract

Since a network is a graph with vertices and edges, many parameters of graph theory have been used in the past to describe communication network stability or vulnerability. The first and most frequently used parameters of a network are vertex-connectivity and edge-connectivity. The higher the vertex-connectivity (edge-connectivity) of a graph the more stable a graph is considered to be. Unfortunately these parameters fail to take into account the fact that the removal of one vertex or one edge may disconnect the graph, but what remains may be very stable. Consequently a number of other parameters have been introduced to measure the stability of a network: toughness, binding number, rate of disruption, neighbor-connectivity, vertex integrity, edge integrity, mean integrity, edge-connectivity vector, l-connectivity and tenacity. In this paper we discuss tenacity and its properties in stability calculation. We indicate relationships between tenacity and connectivity, tenacity and binding number, tenacity and toughness. We also give good lower and upper bounds for tenacity.