Integrity of total transformation graphs
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 member’s being able to communicate with very many others. These communication networks can be modeled through graphs, and we have several graph-theoretic parameters (viz., connectivity, edge-connectivity, tenacity etc.,) 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. The integrity of a graph will consider both the damage and the maximum possible capacity of communication corresponding to the maximum damage to the network. Therefore, we discuss the integrity of total transformation graphs which can help us to reconstruct the given network in such a way that it is more stable than the earlier one. If the network is modeled through total transformation graphs, then there will be increase in the number of nodes and links between the nodes in the obtained network which automatically cause the increase in the stability of the network. In this paper, we obtain the integrity of total transformation graphs of some special class of graphs. Further, we present bounds of integrity of some total transformation graphs of a graph in terms of number of vertices, number of edges and integrity of some derived graph appears as induced subgraph. The expression for integrity of total graph of cycle which was given by Qingfang Ye contained an error. We give correct version of it. In addition, we compute integrity of book graphs.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.6
References
J. Ales and R. Bacik, Strong elemination orderings of the total graph of a tree, Discrete Appl. Math. 39 (1992), 293–295.
A. Aytac and S. Celik, Vulnerability: Integrity of middle graphs, Selcuk J. Appl. Math. 9 (1) (2008), 49–60.
V. Aytac and S. Bodur, Vulnerability of some splitting graphs, Bull. Int. Math. Virtual Inst. 5 (2009), 95–102.
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.
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), 12.
W. Baoyindureng and M. Jixiang, Basic properties of Total Transformation Graphs, J. Math. Study 34 (2) (2001) 109–116.
C.A. Barefoot, R. Entringer and H.C. Swart, Vulnerability in Graphs - A Comparative Survey, J. Combin. Math. Combin. Comp. 1 (1987), 13–22.
C.A. Barefoot, R. Entringer, and H.C. Swart, Integrity of Trees and Powers of Cycles, Congr. Numer. 58 (1987), 103–114.
B. Basavanagoud, Quasi-total graphs with crossing numbers, J. Discrete Math. Cryptography 1 (1998), 133–142.
B. Basavanagoud and V.R. Desai, On the Wiener index of quasi-total graph and its complement, Int. J. Math. Combin. 1 (2016), 82–90.
B. Basavanagoud, P. Jakkannavar, and I.N. Cangul, Integrity of quasi-total graphs, Proceedings of the Jangjeon Mathematical Society 4 (2020), pp. 626–639.
B. Basavanagoud, S. Policepatil, and P. Jakkannavar, Integrity of graph operations, Transactions on Combinatorics (accepted for publication).
D. Baur and R. Tindell, The connectivity of line graphs and total graphs, J. Graph Theory 6 (1982), 197–204.
M. Behzad, Graphs and their chromatic numbers, Ph. D. thesis, Michigan State University, 1965.
M. Behzad, A criterion for the planarity of a total graph, Pro. Camb. Phil. Soc. 63 (1967), 679–681.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
G.T. Chartrand, H. Hevia, E.B. Jarette, and M. Schultz, Subgraph distances in graphs defined by edge transfers, Discrete Math. 170 (1997) 63–79.
P. Dundar and A. Aytac, Integrity of total graphs via certain parameters, ¨ Math. Notes 76 (5) (2004) 665–672.
W.D. Goddard and H.C. Swart, On the Integrity of Combinations of Graphs, J. Combin. Math. Combin. Comp. 4 (1988), 3–18.
W. Goddard and H.C. Swart, Integrity in Graphs, Bounds and Basics, J. Combin. Math. Combin. Comp. 7 (1990), 139–151.
W. Goddard, On the Vulnerability of Graphs, Ph.D. Thesis, University of Natal, Durban, S.A., 1989.
F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
T. Hasunuma, Structural properties of subdivided-line graphs, J. Discrete Algorithms 31 (2015), 69–86.
G. Indulal and A. Vijayakumar, A note on energy of some graphs, MATCH Commun. Math. Comput. Chem. 59 (2008) 269–274.
T. Iqbalunnisa, N. Janakiraman, and N. Srinivasan, Note on iterated total graphs, J. Indian Math. Soc. New Ser. 55 (1990), 67–71.
V.R. Kulli and B. Basavanagoud, Traversability and planarity of quasi-total graphs, Bull. Cal. Math. Soc. 94 (1) (2002), 1–6.
V.R. Kulli, College Graph Theory, Vishwa International Publications, Gulbarga, India, 2012.
H.C. Lu, On large harmonious graph, Ars Combin. 91 (2009), 447–458.
D.V.S. Sastry and B.S.P. Raju, Graph equations for line graphs, total graphs, middle graphs and quasi-total graphs, Discrete Math. 48 (1984), 113–119.
Y. Shang, Subgraph robustness of complex networks under attacks, IEEE Transactions on Systems, Man and Cybernetics: Systems, DOI 10.1109/TSMC.2017.2733545.
Y. Shang, Attack robustness and stability of generalized k-cores, New J. Phys. 21 (2019), 093013.
G.H. Shirdel and A. Mortezaee, Determining the robustness of an interdependent network with a hypergraph model, Electron. J. Graph Theory Appl. 8 (1) (2020), 113–122.
Q. Ye, On vulnerability of power and total graphs, WSEAS Trans. Math. 11 (11) (2012), 1028–1038.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.