Integrity of graph operations

Document Type : Research Paper

Authors

Department of Mathematics, Karnatak University, Dharwad - 580 003, Karnataka, India

Abstract

A communication network can be considered to be highly vulnerable to disruption if the failure of few members (nodes or links) can result in no members being able to communicate with very many others‎. ‎These communication networks can be modeled through graphs‎. ‎There are several graph-theoretic parameters to describe the stability of graphs‎. ‎But‎, ‎these parameters are not sufficient to study stability of graphs‎. ‎This leads to the concept of integrity of a graph‎. ‎In this paper‎, ‎we obtain the integrity of some graph operations and some special graphs which can help us to reconstruct the given network in such a way that it is more stable than the earlier one‎.

Keywords

Main Subjects


[1] M. Atici and A. Kirlangiç, Counter examples to the theorems of integrity of prism and ladders, J. Combin. Math.
Combin. Comp., 34 (2000) 119–127.
[2] K. S. Bagga, L. W. Beineke, W. D. Goddard, M. J. Lipman and R. E. Pippert, A survey of integrity, Discrete Appl.
Math., 37 (1992) 13–28.
[3] K. S. Bagga, L. W. Beineke, M. J. Lipman and R. E. Pippert, The Integrity of the Prism (Preliminary Report),
Abstracts Amer. Math. Soc., 10 (1989) pp. 12.
[4] C. A. Barefoot, R. Entringer and H. C. Swart, Vulnerability in Graphs - A Comparative Survey, J. Combin. Math.
Combin. Comp., 1 (1987) 13–22.
[5] C. A. Barefoot, R. Entringer and H. C. Swart, Integrity of Trees and Powers of Cycles, Congr. Numer., 58 (1987)
103–114.
[6] J. A. Bondy and U. S .R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
[7] W. Gao, W. Wang and Y. Chen, Tight bounds for the existence of path factors in network vulnerability parameter
settings, International Journal of Intelligent System, 2021, https://doi.org/10.1002/int.22.
[8] W. Gao, J. L. G. Guirao and Y. Chen, A toughness condition for fractional (k, m)−deleted graphs revisited, Acta
Math. Sin. (Engl. Ser.), 35 (2019) 1227–1237.
[9] W. Gao, W. Wang and D. Dimitrov, Toughness condition for a graph to be all fractional (g, f, n)−critical deleted,
Filomat, 33 (2019) 2735–2746.
[10] W. D. Goddard and H. C. Swart, On the Integrity of Combinations of Graphs, J. Combin. Math. Combin. Comp.,
4 (1988) 3–18.
[11] W. Goddard and H. C. Swart, Integrity in Graphs, Bounds and Basics, J. Combin. Math. Combin. Comp., 7 (1990)
139–151.
[12] W. Goddard, On the Vulnerability of Graphs, Ph. D. Thesis, University of Natal, Durban, S. A., 1989.
[13] I. Gutman, Kragujec trees and their energy, Ser. A: App. Math. Inform, Mach., 6 (2014) 71–79.
[14] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
[15] V. R. Kulli and N. S. Warad, On the total closed neighborhood graph of a graph, J. Discret. Math. Sci. Cryptography,
4 (2001) 109–144.
[16] V. R. Kulli, College Graph Theory, Vishwa International Publications, Gulbarga, India, 2012.
[17] J. Mycielski, Sur le coloriage des graphs, Colloq. Math., 3 (1955) 161–162.
[18] E. Sampathkumar and H. B. Walikar, On splitting graph of a graph, J. Karnatak Univ. Sci., 25 and 26 (combined)
(1980-81) 13–16.
Volume 10, Issue 3 - Serial Number 3
September 2021
Pages 171-185
  • Receive Date: 20 February 2020
  • Revise Date: 14 March 2021
  • Accept Date: 24 March 2021
  • Published Online: 01 September 2021