New Bounds on Tenacity of Graphs with Small Genus

Affiliation(s)

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

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

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

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

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.

Cite this paper

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.

Jelodar, D. and Moazzami, D. (2014) New Bounds on Tenacity of Graphs with Small Genus.

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.

[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.