On the edge-tenacity of the middle graph of a graph.

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 |+t ( 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 , t( 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. [ABSTRACT FROM AUTHOR]