Computing the Tenacity of Some Graphs

In communication networks, “vulnerability” indicates the resistance of a network to disruptions in communication after a breakdown of some processors or communication links. We may use graphs to model networks, as graph theoretical parameters can be used to describe the stability and reliability of communication networks. In an analysis of the vulnerability of such a graph (or communication network) to disruption, two quantities (there may be others) that are important are: (1) the number of the components in the unaffected graph, (2) the size of the largest connected component. In particular, it is crucial that the first of these quantities be small, while the second is large, in order for one to say that the graph has tenacity. The concept of tenacity was introduced as a measure of graph vulnerability in this sense. The tenacity of a graph is defined as T(G)=min{((|S|+t(G-S))/(w(G-S))):S subset V(G) and w(G-S) 1} where the w (G− S) is the number of components of G − S and t (G − S) is the number of vertices in a largest component of G. In this paper we give some bounds for tenacity and determination of the tenacity of total graphs of specific families of graphs and combinations of these graphs.