Edge-Tenacity

Document Type: Research Paper

Author

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.

Keywords