Document Type : Research Paper


1 University of Tehran, College of Engineering, Faculty of Engineering Science.

2 University of Tehran Department of Algorihthms and Computation, Tehran, Iran


In this paper, we study the edge tenacity of graphs. We will be primarily
interested in edge-tenacious graphs, which can be considered very stable and are somewhat analogous in edge tenacity
to honest graphs in edge-integrity. We show several results about edge-tenacious graphs as well as
find numerous classes of edge-tenacious graphs.
The Cartesian Products of graphs like hypercube, grids, and tori are widely used to design interconnection networks in multiprocessor computing systems.
These considerations motivated us to study tenacity of Cartesian products of graphs. We find the tenacity of Cartesian product of complete graphs (thus setting a conjecture stated in Cozzens and al.) and grids.
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