New Bounds on Tenacity of Graphs with Small Genus

Show more

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.

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.