1. Introduction
The concept of graph tenacity was introduced by Cozzens, Moazzami and Stueckle [1] [2] , as a measure of network vulnerability and reliability. Conceptually graph vulnerability relates to the study of graph intactness when some of its elements are removed. The motivation for studying vulnerability measures is derived from design and analysis of networks under hostile environment. Graph tenacity has been an active area of research since the concept was introduced in 1992. Cozzens et al. in [1] , introduced two measures of network vulnerability termed the tenacity, 
, and the Mix-tenacity, 
, of a graph.
The tenacity 
of a graph 
is defined as
where 
denotes the order (the number of vertices) of a largest component of 
and 
is the number of components of
. A set 
is said to be a 
-set of 
if
.
The Mix-tenacity, 
of a graph 
is defined as
and 
turn out to have interesting properties. Following the pioneering work of Cozzens, Moazzami, and Stueckle, [1] [2] , several groups of researchers have investigated tenacity, and its related problems.
In [3] and [4] Piazza et al. used the Mix-tenacity parameter as Edge-tenacity. This parameter is a combination of cutset 
and the number of vertices of the largest component,
. Also this Parameter didn’t seem very satisfactory for Edge-tenacity, Thus Moazzami and Salehian introduced a new measure of vulnerability, the Edge-tenacity, 
, in [5] .
The Edge-tenacity 
of a graph 
is defined as
where 
denotes the order (the number of edges) of a largest component of
.
The concept of tenacity of a graph 
was introduced in [1] [2] , as a useful measure of the “vulnerability” of
. In [6] , we compared integrity, connectivity, binding number, toughness, and tenacity for several classes of graphs. The results suggest that tenacity is the most suitable measure of stability or vulnerability in that for many graphs, and it is the best able to distinguish among graphs that intuitively should have different levels of vulnerability. In [1] [2] [5] -[22] they studied more about this new invariant.
All graphs considered are finite, undirected, loopless and without multiple edges. Throughout the paper 
will denote a graph with vertex set
. Further the minimum degree will be denoted
, the maximum degree
, connectivity
, the shortest cycle or girth 
and we use 
to denote the independence number of 
.
The genus of a graph is the minimal integer 
such that the graph can be drawn without crossing itself on a sphere with 
handles. Thus, a planar graph has genus 0, because it can be drawn on a sphere without self-crossing. In topological graph theory there are several definitions of the genus of a group. Arthur T. White introduced the following concept. The genus of a group 
is the minimum genus of a (connected, undirected) Cayley graph for
. The graph genus problem is NP-complete.
A graph 
is toroidal if it can be embedded on the torus. In other words, the graphs vertices can be placed on a torus such that no edges cross. Usually, it is assumed that 
is also non-planar.
Proposition 1 (a) If 
is a spanning subgraph of
, then
.
b)
, where
.
Proposition 2 If 
is any noncomplete graph,
.
Proposition 3 If 
is a nonempty graph and 
is the largest integer such that 
is an induced subgraph of
, then
.
Corollary 1 a) If 
is noncomplete and claw-free the
.
b) If 
is a nontrivial tree then
.
c) If 
is r-regular and r-connected then
.
The following well-known results on genus will be used.
Proposition 4 If 
is a connected graph of genus
, connectivity
, girth
, having 
vertices, 
edges and 
regions, then a) 
b) 
[23]
c) 
[24]
2. Lower Bound
In this section we establish lower bounds on the tenacity of a graph in terms of its connectivity and genus.
We begin by presenting a theorem due to Schmeichel and Bloom.
Theorem 2.1 (Schmeichel and Bloom [25] ) Let G be a graph with genus
. If 
has connectivity
, with
, then
for all 
with
.
It is now to drive the bounds on the tenacity that we seek.
Theorem 2.2 If 
is a connected graph of genus 
and connectivity
, then a)
, if 
or
, and b)
, if
.
Proof. First, note that the inequalities hold trivially if 
or
. So suppose
.
First, suppose that
. Let 
be a 
-set. Then since
, by Theorem 2.1 we have
So
. Since
, 
and hence
. Therefore,
if
, we have 
then
and part (a) is proved.
So suppose
. Again, let 
be a 
-set in
. Then
and thus
and 
, so
the result follows.
The above bounds is illustrated by a subset of the complete bipartite graph. Let 
and 
be integer such that 
is a multiple of 
and
. Then 
has connectivity
, genus 
and tenacity
.
2.1. Planar Graphs and the Lower Bound of Tenacity
We next investigate the bounds provided above if 
is a planar or toroidal graph. To this end we require the definition of a Kleetope, 
, of an embedding 
of a graph. If 
is a graph embedded with regions
, then 
is the graph obtained from 
by, for
, inserting a vertex 
into the interior of 
and joining 
to each vertex on the boundary of
. Note that the embedding of 
extends naturally to an embedding of
. In particular, if 
is a plane graph then so is
. Kleetopes are sometimes used as examples of graphs with maximum independence number for given genus and connectivity (see [26] ).
The bound in Theorem 2.2a is not sharp for 
and
. But the following examples show that the bound is suitable for 
and all possible values of
. Furthermore, such examples can be obtained with the maximum girth allowed for such connectivity. Note that by proposition 4a, if 
is the girth,
Example 1
a) For 
the girth can be arbitrarily large. For 
consider the graph 
obtained by taking 
disjoint copies of the path 
on 
vertices and identifying the corresponding ends into two vertices. This is a planar graph with tenacity 
as 
and girth
.
b) For 
the girth is at most
. A generalized Herschel graph 
is defined as follows. Form a cyclic chain of 4-cycles by taking 
disjoint 4-cycles
, 
, and identifying 
and 
(including 
and
). Then introduce vertices 
and 
and make 
adjacent to each 
and make 
adjacent to each
. The result is a 3-connected planar graph of girth 4, (see Figure 1). Now, let 
be obtained by replacing each of the 
and 
by dodecahedron as follows. To make notation simpler we explain how to replace a generic node 
of degree 3 with a dodecahedron
. Suppose the outer cycle of 
is 
in clockwise order and the neighbors of 
are 
and 
in clockwise order. Then replace 
and its incident edges by 
and the edges 
and
. The resulting graph 
is 3-connected (recall that the dodecahedron is 3-connected), planar, and has girth 5.
Furthermore, for 
,
Figure 1. Part of the 3- connected planar graph with
.
while 
.
c) If 
then
. Let 
be a ladder graph with two rails and 
rungs between them. Rails be 
with vertices 
and 
with vertices
. Now make
, introduce vertices 
and 
and make a adjacent to each 
and b adjacent to each
. 
is a planar graph with 
and
, (see Figure 2). For
,
whereas
.
d) if 
then
. For positive integer 
the graph 
is defined inductively as follows: 
is a 
vertices cycle with 
in clockwise order and 
is a 
vertices cycle with 
in clockwise order.
Make two edges between 
and vertices 
and
, then introduce 
and
, make edges 
and 
(note that
), in Figure 3 you can see a 
graph with empty cycle vertices as set of 
and empty rectangle vertices as set of
. Suppose that 
is cut set and
, then
whereas 
.
2.2. Toroidal Graphs
We next consider toroidal graphs in more depth. For 
we provide graphs with 
and maximum girth.
Example 2 (a) For 
and
, the family graphs described in Example 1(a) for planar graphs shows that 2-connected graphs can have tenacity arbitrarily close to 1. (Examples specifically with genus 1 can be obtained by adding two edges to
, for
).
b) For 
then
. The graph
, for 
an even integer has genus 1, connectivity 4, 
(since, for example, its bipartite and hamiltonian) and girth 4.
c) If 
then
. Consider the following graph 
where every region is a pentagon: Let 
and 
where addition is taken modulo
. The graph 
is shown in Figure 4.
We note that 
is toroidal with a pentagonal embedding. Let
. Then
, 
, 
.
d) If 
then
. Consider the cubic bipartite “honeycomb” graph 
on 
vertices where every region is a hexagon. Then
, satisfies 
and
.
e) If 
then
. Consider any (3-connected) bipartite graph 
which has partite sets 
and 
where every vertex in 
has degree 3 and every vertex in 
has degree 6 and is embedded in the torus with every region a quadrilateral. For example,
. Such an 
can also be obtained by modifying the honeycomb graph
, depicted in Figure 5 as follows: If the bipartite sets for
, are 
and
, then add in each region a new vertex and join it to the three vertices of 
on the boundary of the region; the new vertices are added to
. Now form 
by taking
, and replacing every vertex of degree 3 by a dodecahedron as described in Example 1(b). The resulting graph 
satisfies
, 
and
.
Figure 2. Part of planar graph with 
and
.
The graph 
constructed in Example 2(e) has girth
. The lower bound given in Theorem 2.2(b) cannot be obtained if 
and 
as is shown next.
Lemma 2.3 If 
is a graph with 
and
, then
.
Proof. Let 
be a toroidal graph satisfying the hypothesis of the lemma. Then Euler?s formula (or Proposition 4(a)) shows that the graph is 3-regular. So by Corollary 1(c) the tenacity is at least 1.
3. Conclusions
The sharpness of the bound
, if 
is illustrated by a subset of the complete bipartite graph. Let 
and 
be integer so that 
is a multiple of 
and
. Then 
has connectivity
, genus 
and tenacity
. So the bound in Theorem 2.2(b) is attained by an infinite class of graphs, all of girth 4.
The bound in Theorem 2.2(a) is not sharp for 
and 
. But the examples 1 showed that the bound is sharp for 
and all possible values of
.
For Toroidal graphs when 
we introduced graphs with 
and maximum girth.
Acknowledgements
This work was supported by Tehran University. Our special thanks go to the University of Tehran, College of Engineering and Department of Engineering Science for providing all the necessary facilities available to us for successfully conducting this research. We would like to thank Center of Excellence Geomatics Engineering and Disaster Management for partial support of this research. Also we would like to thank School of Computer Sciences, Institute for Research in Fundamental Sciences (IPM), P.O. Box: 19395-5746, Tehran, Iran, for partial support of this research.
NOTES
*Corresponding author.