Department of Algorithms and Computation, Faculty of Engineering Science, College of Engineering, University of Tehran, Iran,
Abstract
The edge-tenacity $T_e(G)$ of a graph G was defined as \begin{center} $T_e(G)=\displaystyle \min_{F\subset E(G)}\{\frac{\mid F\mid +\tau(G-F)}{\omega(G-F)}\}$ \end{center} where the minimum is taken over all edge cutset F of G. We define G-F to be the graph induced by the edges of $E(G)-F$, $\tau(G-F)$ is the number of edges in the largest component of the graph induced by G-F and $\omega(G-F)$ is the number of components of $G-F$. A set $F\subset E(G)$ is said to be a $T_e$-set of G if \begin{center} $T_e(G)=\frac{\mid F\mid+\tau(G-F)}{\omega(G-F)}$ \end{center} Each component has at least one edge. In this paper we introduce a new invariant edge-tenacity, for graphs. it is another vulnerability measure. we present several properties and bounds on the edge-tenacity. we also compute the edge-tenacity of some classes of graphs.
)