New Bounds on Tenacity of Graphs with Small Genus

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 well-known graphical parameters are considered, and another formulation introduced from further bounds are derived.

Share and Cite:

Jelodar, D. and Moazzami, D. (2014) New Bounds on Tenacity of Graphs with Small Genus. Open Journal of Discrete Mathematics, 4, 28-35. doi: 10.4236/ojdm.2014.42005.

Conflicts of Interest

The authors declare no conflicts of interest.

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
[26] Grunbaum, B. (1967) Convex Polytopes. Wiley, New York, 217.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.