Open Journal of Discrete Mathematics
Vol.4 No.2(2014), Article ID:44837,8 pages DOI:10.4236/ojdm.2014.42005

New Bounds on Tenacity of Graphs with Small Genus

Davoud Jelodar1, Dara Moazzami2,3,4*

1Department of Algorithms and Computation, University of Tehran, Tehran, Iran

2Department of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran

3School of Computer Sciences, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran

4Center of Excellence in Geomatics Engineering and Disaster Management, University of Tehran, Tehran, Iran

Email: *dmoazzami@ut.ac.ir

Copyright © 2014 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 15 January 2014; revised 14 February 2014; accepted 12 March 2014

ABSTRACT

A new lower bound on the tenacity of a graph G in terms of its connectivity and genus is obtained. The lower bound and interrelationship involving tenacity and other wellknown graphical parameters are considered, and another formulation introduced from further bounds are derived.

Keywords:Tenacity Parameter, Connectivity, Genus, Planar Graph, Torus

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.               

Figure 3. A graph with and.                       

Figure 4. Pentagonal embedding graph.                       

Figure 5. A honeycomp graph.                              

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.

References

  1. Cozzens, M.B., Moazzami, D. and Stueckle, S. (1995) The Tenacity of a Graph. Graph Theory. In: Alavi, Y. and Schwenk, A., Eds., Combinatorics, and Algorithms, Wiley, New York, 1111-1112.
  2. Cozzens, M.B., Moazzami, D. and Stueckle, S. (1994) The Tenacity of the Harary Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 16, 33-56.
  3. Piazza, B., Roberts, F. and Stueckle, S. (1995) Edge-Tenacious Networks. Networks, 25, 7-17.
  4. Piazza, B. and Stueckle, S. (1999) A Lower Bound for Edge-Tenacity. Congressus Numerantium, 137, 193-196.
  5. Moazzami, D. and Salehian, S. (2008) On the Edge-Tenacity of Graphs. International Mathematical Forum, 3, 929-936.
  6. Moazzami, D. (1999) Vulnerability in Graphs—A Comparative Survey. Journal of Combinatorial Mathematics and Combinatorial Computing, 30, 23-31.
  7. Ayta, A. (2005) On the Edge-Tenacity of the Middle Graph of a Graph. International Journal of Computer Mathematics, 82, 551-558.
  8. Choudum, S.A. and Priya, N. (1999) Tenacity of Complete Graph Products and Grids. Networks, 34, 192-196.
  9. Choudum, S.A. and Priya, N. (2001) Tenacity-Maximum Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 37, 101-114.
  10. Li, Y.K. and Wang, Q.N. (2008) Tenacity and the Maximum Network. Chinese Journal of Engineering Mathematics, 25, 138-142.
  11. Li, Y.K., Zhang, S.G., Li, X.L. and Wu, Y. (2004) Relationships between Tenacity and Some Other Vulnerability Parameters. Basic Sciences Journal of Textile Universities, 17, 1-4.
  12. Ma, J.L., Wang, Y.J. and Li, X.L. (2007) Tenacity of the Torus. Journal of Northwest Normal University Natural Science, 43, 15-18.
  13. Moazzami, D. (2000) Stability Measure of a Graph—A Survey. Utilitas Mathematica, 57, 171-191.
  14. Moazzami, D. (2001) On Networks with Maximum Graphical Structure, Tenacity T and Number of Vertices. Journal of Combinatorial Mathematics and Combinatorial Computing, 39,121-126.
  15. Moazzami, D. (1999) A Note on Hamiltonian Properties of Tenacity. Proceedings of the International Conference, Budapest, 4-11 July 1999, 174-178.
  16. Moazzami, D. and Salehian, S. (2009) Some Results Related to the Tenacity and Existence of K-Trees. Discrete Applied Mathematics, 8, 1794-1798. http://dx.doi.org/10.1016/j.dam.2009.02.003
  17. Wang, Z.P., Ren, G. and Zhao, L.C. (2004) Edge-Tenacity in Graphs. Journal of Mathematical Research and Exposition, 24, 405-410.
  18. Wang, Z.P. and Ren, G. (2003) A New Parameter of Studying the Fault Tolerance Measure of Communication Networks—A Survey of Vertex Tenacity Theory. Advanced Mathematics, 32, 641-652.
  19. Wang, Z.P., Ren, G. and Li, C.R. (2003) The Tenacity of Network Graphs—Optimization Design. I. Journal of Liaoning University Natural Science, 30, 315-316.
  20. Wang, Z.P., Li, C.R., Ren, G. and Zhao, L.C. (2002) Connectivity in Graphsa Comparative Survey of Tenacity and Other Parameters. Journal of Liaoning University Natural Science, 29, 237-240 (in Chinese).
  21. Wang, Z.P., Li, C.R., Ren, G. and Zhao, L.C. (2001) The Tenacity and the Structure of Networks. Journal of Liaoning University Natural Science, 28, 206-210.
  22. Wu, Y. and Wei, X.S. (2004) Edge-Tenacity of Graphs. Chinese Journal of Engineering Mathematics, 21, 704-708.
  23. Ringel, G. (1965) Das Geschlect des vollständiger paaren Graphen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 28, 139-150. http://dx.doi.org/10.1007/BF02993245
  24. Ringel, G. (1974) Map Color Theorem, Die Grundlehren der mathematischen Wissenchaften Band. Vol. 209, Springer, Berlin.
  25. Schmeichel, E.F. and Bloom, G.S. (1979) Connectivity, Genus and the Number of Components in Vertex-Deleted Subgraphs. Journal of Combinatorial Theory, Series B, 27, 198-201. http://dx.doi.org/10.1016/0095-8956(79)90081-9

NOTES

*Corresponding author.