INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, vol.82, no.5, pp.551-558, 2005 (Journal Indexed in SCI)
We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S) = [\S\ + tau(G - S)]/[w(G - S)]. Formally, the edge-tenacity of a graph G is defined as T'(G) = min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T'-set of G if T'(G) = sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, tau(G - S) is the number of vertices in the largest component of G - S and w(G - S) is the number of components of G - S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.