Ratio Mathematica Volume 40, 2021, pp. 27-46 Integrity of generalized transformation graphs Bommanahal Basavanagoud∗ Shruti Policepatil† Abstract The values of vulnerability helps the network designers to construct such a communication network which remains stable after some of its nodes or communication links are damaged. The transformation graphs considered in this paper are taken as model of the network system and it reveals that, how network can be made more stable and strong. For this purpose the new nodes are inserted in the network. This construction of new network is done by using the definition of generalized transformation graphs of a graphs. Integrity is one of the best vulnerability parameter. In this paper, we investigate the in- tegrity of generalized transformation graphs and their complements. Also, we find integrity of semitotal point graph of combinations of basic graphs. Finally, we characterize few graphs having equal in- tegrity values as that of generalized transformation graphs of same structured graphs. Keywords: Vulnerability; connectivity; integrity; generalized trans- formation graphs; semitotal point graph. 2020 AMS subject classifications: 05C40, 90C35.1 ∗Department of Mathematics, Karnatak University, Dharwad - 580 003, Karnataka, India; b.basavanagoud@gmail.com. †Department of Mathematics, Karnatak University, Dharwad - 580 003, Karnataka, India; shru- tipatil300@gmail.com. 1Received on February 25th, 2021. Accepted on June 23th, 2021. Published on June 30th, 2021. doi: 10.23755/rm.v40i1.576. ISSN: 1592-7415. eISSN: 2282-8214. c©The Authors. This paper is published under the CC-BY licence agreement. 27 Bommanahal Basavanagoud, Shruti Policepatil 1 Introduction The stability of a communication network composed of processing nodes and communication links are of prime importance to network designers. As the net- work begins losing links or nodes, eventually there will be a decrease to certain extent in its effectiveness. Thus, communication networks must be constructed as stable as possible; not only with respect to the initial disruption, but also with re- spect to the possible reconstruction of the network. In the analysis of vulnerability of a communication network we often consider the following quantities: 1. the number of members of the largest remaining group within mutual communication can still occur, 2. the number of elements that are not functioning. The communication network can be represented as an undirected graph. Con- sequently, a number of other parameters have recently been introduced in order to attempt to cope up with this difficulty. Tree, mesh, hypercube and star graphs are popular communication networks. If we think of graph as modeling a net- work, there are many graph theoretical parameters used in the past to describe the stability of communication networks. Most notably, the vertex-connectivity and edge-connectivity have been frequently used. The best known measure of reliabil- ity of a graph is its vertex-connectivity. The difficulty with these parameters is that they do not take into account what remains after the graph has been disconnected. To estimate these quantities, the concept of integrity was introduced by Barefoot et al. in [6] as a measure of the stability of a graph. The integrity of a graph G is defined in [6] as I(G) = min S⊂V (G) {|S|+ m(G−S)}, where m(G − S) denotes the order of the largest component of G − S. In [6], the authors have compared integrity, connectivity, toughness and binding number for several classes of graphs. In 1987, Barefoot et al. [7] have investigated the integrity of trees and powers of cycles. In 1988, Goddard et al. [14] have obtained integrity of the join, union, product and composition of two graphs. The integrity of a small class of regular graphs was studied by Atici et al. [1].The authors in [3, 20] have studied the integrity of cubic graphs. For more details on integrity of a graph refer to [2, 4, 5, 11–13, 15]. In this paper, we are concerned with nontrivial, simple, finite, undirected graphs. Let G be a graph with a vertex set V (G) and an edge set E(G) such that |V (G)| = n and |E(G)| = m. The degree of a vertex dG(v) is the number of edges incident to it in G. The symbol dxe denotes the smallest integer that is greater than or equal to x and bxc denotes the greatest integer smaller than or equal to x. For undefined graph theoretic terminologies and notations refer to [16] or [17]. 28 Integrity of generalized transformation graphs 2 Preliminaries 2.1 Basic results on integrity In this subsection, we review some of the known results about integrity of graphs. Theorem 2.1. [5] The integrity of (i) complete graph Kn, I(Kn) = n, (ii) null graph Kn, I(Kn) = 1, (iii) star K1,b, I(K1,b) = 2, (iv) path Pn, I(Pn) = d2 √ n + 1e−2, (v) cycle Cn, I(Cn) = d2 √ ne−1, (vi) complete bipartite graph Ka,b, I(Ka,b) = 1 + min{a,b}, (vii) wheel Wn, I(Wn) = d2 √ n−1e. 3 Generalized transformation graphs Sampathkumar and Chikkodimath [19] defined the semitotal-point graph T2(G) as the graph whose vertex set is V (G)∪E(G), and where two vertices are adjacent if and only if (i) they are adjacent vertices of G or (ii) one is a vertex of G and other is an edge of G incident with it. Inspired by this definition, Basavanagoud et al. [9] introduced some new graphical transformations. These generalize the concept of semitotal-point graph. Let G = (V,E) be a graph, and let α, β be two elements of V (G) ∪ E(G). We say that the associativity of α and β is + if they are adjacent or incident in G, otherwise is −. Let xy be a 2-permutation of the set {+,}. We say that α and β correspond to the first term x of xy if both α and β are in V (G), whereas α and β correspond to the second term y of xy if one of α and β is in V (G) and the other is in E(G). The generalized transformation graph Gxy of G is defined on the vertex set V (G)∪E(G). Two vertices α and β of Gxy are joined by an edge if and only if their associativity in G is consistent with the corresponding term of xy. We denote the complement of the generalized transformation graph Gxy by Gxy. In view of above, one can obtain four graphical transformations of graphs, since there are four distinct 2-permutations of {+,−}. Note that G++ is just the semitotalpoint graph T2(G) of G, whereas the other generalized transformation graphs are G+−, G−+ and G−−. 29 Bommanahal Basavanagoud, Shruti Policepatil b b b b bc bc bc bc bc bc bc bc b b b b b b bbbc bc bc bc bc b b b b b b b b b b b b b bc bc bc bc bc bc bc bc bc bc bc bc b b b b b b b b b b b b bb b bc bc bc bc bc bc bc bcbc bc bc bc b b b b b b b b b b b b b b b b bc bc bc bc G++ G+− G−+ G −− G++ G+− G−+ G −− b b b b G : v1 v2 v3 v4 v1 v1 v1 v1 v1v1 v1 v1 e1 e2 e3 e4 v2 v2 v2 v2 v3 v4 v3 v4v3 v4v3 v4 v2 v3 v4 v2 v2 v2 v3 v4v3 v4v3 v4 e1 e2 e3 e4 e3 e1 e4 e2 e1 e3 e4 e2 e3 e2 e1 e4 e4 e3 e1 e2 e1 e2 e3 e4 e4e3 e2 e1 e1 e2 e3 e4 Figure 1: Graph G, its generalized transformation Gxy and their complements Gxy The generalized transformation graph Gxy, introduced by Basavanagoud et al. [9], is a graph whose vertex set is V (G) ∪ E(G), and α,β ∈ V (Gxy). The vertices α and β are adjacent in Gxy if and only if (a) and (b) holds: (a) α,β ∈ V (G), α,β are adjacent in G if x = + and α,β are nonadjacent in G if x = − (b) α ∈ V (G) and β ∈ E(G), α,β are incident in G if y = + and α,β are nonincident in G if y = − An example of generalized transformation graphs and their complements are shown in Figure 1. The vertex v of Gxy corresponding to a vertex v of G is referred to as a point vertex. The vertex e of Gxy corresponding to an edge e of G is referred to as a line vertex. For more details on generalized transformation graphs, refer to [8–10, 17–19]. 4 Main results In this section, we determine the integrity of semitotal point graph(G++) of some standard families of graphs. Also, the integrity of generalized transforma- 30 Integrity of generalized transformation graphs tion graphs G+−, G−+, G−−, G++, G+−, G−+ and G−− are obtained. Then, we calculate integrity of semitotal point graph of cartesian product and composition of some graphs 4.1 Integrity of generalized transformation graphs Theorem 4.1. For a graph Pn (n ≥ 4), I(P++n ) = { d2 √ 2ne−2, if n is odd, d2 √ 2n−1e−1, if n is even. Proof. Let S be a subset of V (P++n ). The number of remaining components after removing |S| = r vertices is given in Table 1 and Table 2. Case 1. Suppose n is even. The number of vertices in P++n is 2n−1. If r vertices are removed from graph P++n , then one of the connected components has at least 2n−1−r r vertices. So, the order of the largest component is m(P++n −S) ≥ 2n−1−rr . So I(P++n ) ≥ min { r + 2n−1− r r } . The function r + 2n−1−r r takes its minimum value at r = √ 2n−1. If we substi- tute the minimum value in the function, then we have I(P++n ) = 2 √ 2n−1 − 1. Since the integrity is integer valued, we round this up to get a lower bound. So the integrity of P++n is, I(P ++ n ) = d2 √ 2n−1e−1. Number of removing vertices 1 2 3 ... r Number of remaining components 1 2 3 ... r Table 1: n is even Number of removing vertices 1 2 3 ... r Number of remaining components 2 3 4 ... r + 1 Table 2: n is odd Case 2. Suppose n is odd. Since the number of vertices in P++n is 2n − 1 and m(P++n −S) ≥ 2n−1−rr+1 , we have I(P ++ n ) ≥ min{r+ 2n−1−rr+1 }. After the required elementary arithmetical operations, we get I(P++n ) = d2 √ 2ne−2. 31 Bommanahal Basavanagoud, Shruti Policepatil Example 4.1. Consider a graph P5 and its semitotal point graph P++5 . Let S = {a,b}⊂ V (P++5 ) (see Figure 2) such that |S| = 2 and m(P++5 −S) = 3. So, I(P++5 ) = 5. b b bb b b b b bbc bc bc bcbc bc bc bc P ++5 : P ++5 − S : b b b b b b bc bc bcbc a b Figure 2: Graph P++5 −S. Theorem 4.2. For a cycle Cn of length n ≥ 4, I(C++n ) = { ⌈ n 2 ⌉ + 3, if n(≤ 7) is odd and n(≤ 16) is even,⌈ n 3 ⌉ + 5, if n(≥ 9) is odd and n(≥ 18) is even. Proof. C++n has 2n vertices and 3n edges. Let S ⊂ V (C++n ). Case 1. Suppose n(≤ 7) is odd and n(≥ 16) is even. Choose a set S in such a way that it is an independent set of vertices of Cn. It is clear that |S| = ⌈ n 2 ⌉ = β0(Cn) and m(C++n −S) = 3. So, I(C++n ) = ⌈ n 2 ⌉ + 3. Case 2. Suppose n(≥ 9) is odd and n(≤ 18) is even. Choose a set S in such a way that it is an independent set of vertices of Cn having distance 3 in between them. It is clear that |S| = ⌈ n 3 ⌉ and m(C++n −S) = 5. So, I(C++n ) = ⌈ n 3 ⌉ + 5. Example 4.2. Consider a graph C6 and its semitotal point graph C++6 . Let S = {a,b,c}⊂ V (C++6 ) (see Figure 3) such that |S| = 3 and m(C++6 −S) = 3. So, I(C++6 ) = 6. Theorem 4.3. For a complete graph Kn of order n ≥ 2, I(K++n ) = n + 1. Proof. K++n has n(n+1) 2 vertices and 3n(n−1) 2 edges. Let S ⊂ V (K++n ) be a set containing all the vertices of Kn. So, |S| = n. The removal of vertices from K++n leaves a totally disconnected graph with n(n−1) 2 vertices. Hence, m(K++n −S) = 1. Therefore, |S| + m(K++n − S) = n + 1 is minimum for above set S. Then it is clear that, I(K++n ) = n + 1. 32 Integrity of generalized transformation graphs b b b b b b b b b b bbbc bc bc bc bc bc C++6 : a bc b b b b b b b b b bc bc bc bc bc bc C++6 − S: Figure 3: Graph C++6 −S. Example 4.3. Consider a graph K4 and its semitotal point graph K++4 . Let S = {a,b,c,d}⊂ V (K++4 ) (see Figure 4). It is clear that m(K++4 −S) = 1. So, I(K++4 ) = 5. b b b b b b b b b b b K++4 : bc bc bc bc bc bc K++4 − S: b b b b b b bc bc bc bc bc bc a b c d Figure 4: Graph K++4 −S. Corolary 4.1. I(Kp) = I(K++q ) if and only if p = q + 1. Theorem 4.4. For a complete bipartite graph Ka,b of order a + b, I(K++a,b ) = 2min{a,b}+ 1. Proof. K++a,b has 2ab vertices and 3ab edges. Let us select S in such a way that it should contain minimum number of vertices among two partite sets of Ka,b. So, |S| = min{a,b}. The deletion of vertices of S from K++a,b results in union of stars K1,min{a,b}. Hence, m(K ++ a,b −S) = min{a,b}+1. The value of |S|+m(K++a,b −S) whose sum is minimum for chosen S. Therefore, I(K++a,b ) = 2min{a,b}+1. Example 4.4. Consider a graph K2,3. Let S = {a,b}⊂ V (K++2,3 ) (see Figure 5). It is clear to write |S| = 2 and m(K++2,3 −S) = 3. So, I(K++2,3 ) = 5. Corolary 4.2. I(Ka1,b1) = I(K ++ a2,b2 ) if and only if min{a1,b1} = 2min{a2,b2}. K2,2 and K1,2 are the smallest graphs satisfying above condition such that I(K2,2) = I(K++1,2 ). 33 Bommanahal Basavanagoud, Shruti Policepatil b b b b b b b bb b b bc bc bc bc bc bc K++2,3 : b b b b b b b b b bc bc bc bc bc bc K++2,3 − S: a b Figure 5: Graph K++2,3 −S. Theorem 4.5. For a star K1,b of order b + 1, I(K++1,b ) = 3. Proof. K++1,b has 2b + 1 vertices and 3b edges. Let S ⊂ V (K++1,b ) containing a central vertex of K1,b. So, |S| = 1. The removal of a vertex of set S from K++1,b results in graph bK2. Hence, m(K ++ 1,b −S) = 2. The value |S|+ m(K++1,b −S) is minimum for the chosen S. Therefore, I(K++1,b ) = 3. Remark 4.1. The values of integrity of star graph and integrity of semitotal point graph of star graph are never same, since I(K1,b) = 2 and I(K ++ 1,b ) = 3. Example 4.5. Consider a graph K1,3. Let S = {a}⊂ V (K++1,3 ) (see Figure 6). It is clear to write |S| = 1 and m(K++1,3 −S) = 2 So, I(K++1,3 ) = 3 b b b b b b bbc bc bc K++1,3 : K ++ 1,3 − S: b b b b b b bc bc bc a Figure 6: Graph K++1,3 −S. Theorem 4.6. For a wheel Wn of order n ≥ 5, I(W++n ) = ⌈ n−1 2 ⌉ + 5. 34 Integrity of generalized transformation graphs Proof. W++n has 3n−2 vertices and 6(n−1) edges. Let S ⊂ V (W++n ). Case 1. Suppose n is odd Clearly, the order of an outer cycle of wheel is n−1, which is even. Choose a set S1 in such a way that it is an independent set of vertices of Cn−1. It is clear that |S1| = n−12 = β0(Cn−1). Case 2. Suppose n is even Clearly, the order of an outer cycle of wheel is n − 1, which is odd. Let S2 be an independent set of vertices of Cn−1 such that |S2| = n−22 . Let v1 be a vertex of V (Cn−1) \ S2 such that v1 is adjacent to a vertex of S2 as well as to a vertex V (Cn)\S2. Let us take S1 = S2 ∪{v} and hence |S1| = n2 . Combining the above two cases we get, |S1| = ⌈ n−1 2 ⌉ , for all n, Let v2 be a central vertex of Wn. Let us define a set S in such a manner that S = S1 ∪{v2}. It is to be noted that |S| = ⌈ n−1 2 ⌉ + 1. The deletion of vertices of set S from W++n gives a graph whose components are P4’s and K1’s. Hence, m(W++n −S) = 4. The set S defined in this manner gives minimum value of |S|+m(W++n −S). Therefore, I(W++n ) = ⌈ n−1 2 ⌉ + 5. Corolary 4.3. I(Wp) = I(W++q ) if and only if d2 √ p−1e = ⌈ q−1 2 ⌉ + 5. W11 and W5 are the smallest graphs which satisfy the above condition such that I(W11) = I(W ++ 5 ). Example 4.6. Consider a graph W7. Let S = {a,b,c,d}⊂ V (W++7 ) (see Figure 7). It is clear to write |S| = 4 and m(W++7 −S) = 4. So, I(W++7 ) = 8 b b b b b b b b bb b b bb b b b b b b bc bc bc bc bcbc bc bc bc bc bc bc W ++7 : W ++ 7 − S: b b b b b b b b b b b b b bb bc bc bc bc bc bc bc bc bc bc bc bc a c d b Figure 7: Graph W++7 −S. Theorem 4.7. For a connected graph G � K1,b of order n and size m, I(G+−) = n + 1. Proof. For an (n,m) graph G, G+− has n + m vertices and m(n−1) edges. The n vertices have degree m and m vertices have n− 2 in G+−. Let S ⊂ V (G+−). Consider a set S consisting a vertices of G+− which corresponds to the vertices of 35 Bommanahal Basavanagoud, Shruti Policepatil a graph G. Then it is clear that |S| = n. The removal of the vertices of set S from G+− results in a null graph Km. Hence, m(G+−−S) = 1. |S|+ m(G+−−S) is minimum for above chosen S. Therefore, I(G+−) = n + 1.. Theorem 4.8. For a star K1,b (b ≥ 3), I(K+−1,b ) = b + 1. Proof. For a star K1,b of order b+ 1 and size b, the graph K +− 1,b has 2b+ 1 vertices and b2 edges. Let S ⊂ V (K+−1,b ). Choose as set S in such a way that it should contain the pendant vertices of K1,b. So, |S| = b. The deletion of the vertices of set S from K+−1,b results in null graph Kb+1. So, m(K +− 1,b −S) = 1. |S|+m(K+−1,b −S) is minimum for above chosen S. Therefore, I(K+−1,b ) = b + 1. The column 2 and 4 of Table Table 3 shows integrity of basic graphs and integrity of transformation graph G+− of graphs with same structure. G I(G) G+− I(G+−) G−+ I(G−+) G−− I(G−−) P6 4 P +− 3 4 P −+ 3 4 P −− 3 4 P10 5 P +− 10 11 P −+ 10 8 P −− 10 11 C5 4 C +− 3 4 C −+ 3 4 C −− 3 4 C7 5 C +− 7 8 C −+ 7 8 C −− 7 8 Kn n K +− n n + 1 K −+ n n + 1 K −− n n + 1 K5,5 6 K +− 2,3 6 K −+ 2,3 6 K −− 2,3 6 K5,6 6 K +− 5,6 12 K −+ 5,6 12 K −− 5,6 12 K1,b 2 K +− 1,b b + 1 K −+ 1,b b + 2 K −− 1,b b + 1 W8 6 W +− 5 6 W −+ 5 6 W −− 5 6 W9 6 W +− 9 10 W −+ 9 10 W −− 9 10 Table 3: Theorem 4.9. For a connected graph G � K1,b of order n and size m, I(G−+) = n + 1. Proof. For an (n,m) graph G, G−+ has n+m vertices and n(n−1) 2 +m edges. The n vertices have degree 2 in G−+. Let S ⊂ V (G−+). Consider a set S consisting a vertices of G−+ which corresponds to the vertices of a graph G. Then it is clear that |S| = n. The removal of the vertices of set S from G−+ results in a null graph Km. Hence, m(G−+ − S) = 1. The value |S| + m(G−+ − S) is minimum for above chosen S. Therefore, I(G−+) = n + 1. 36 Integrity of generalized transformation graphs The column 2 and 6 of Table 3 shows integrity of basic graphs and integrity of transformation graph G−+ of graphs with same structure. Theorem 4.10. For a star K1,b (b ≥ 3), I(K−+1,b ) = b + 1. Proof. The proof is similar to that of Theorem 4.8. Theorem 4.11. For a connected graph G � K1,b of order n and size m, I(G−−) = n + 1. Proof. For an (n,m) graph G, G−− has n + m vertices and n(n−1) 2 + m(n − 3) edges. Let S ⊂ V (G−−). Consider a set S consisting a vertices of G−− which corresponds to the vertices of a graph G. Then it is clear that |S| = n. Deleting the vertices of set S from G−− results in a null graph Km. Hence, m(G−−−S) = 1. |S| + m(G−− − S) is minimum for above chosen S. Therefore, I(G−−) = n + 1. Theorem 4.12. For a star K1,b(b ≥ 3), I(K−−1,b ) = b + 1. Proof. For a star K1,b of order b+1 and size b, the graph K −− 1,b has 2b+1 vertices. Let S ⊂ V (K−−1,b ). Choose as set S in such a way that it should contain the pendant vertices of K1,b. So, |S| = b. The deletion of the vertices of set S from K−−1,b results in null graph Kb+1. So, m(K −− 1,b − S) = 1. |S| + m(K−−1,b − S) is minimum for above chosen S. Therefore, I(K−−1,b ) = b + 1. The column 2 and 8 of Table 3 shows integrity of basic graphs and integrity of transformation graph G−− of graphs with same structure. Theorem 4.13. For any connected graph G of order n and size m ≥ 2, I(G++) = n + m−2. Proof. For a connected graph G of order n and size m ≥ 2, G++ has order n + m. Let S ⊂ V (G++). Consider a set S containing all the vertices and edges of G except one edge and its incident vertices. So, |S| = n + m− 3. The removal of the vertices of set S from G++ gives 3K1. Hence, m(G++ −S) = 1. The value |S| + m(G++ − S) is minimum for the selected subset S. Therefore, I(G++) = n + m−2.. 37 Bommanahal Basavanagoud, Shruti Policepatil Theorem 4.14. For any connected graph G of order n and size m ≥ 2, I(G+−) = n + m−2. Proof. For a connected graph G of order n and size m ≥ 2, G+− has order n + m. Let S ⊂ V (G+−). Consider a set S containing all the vertices and edges of G except one edge and two nonincident vertices(adjacent vertices). So, |S| = n + m − 3. The removal of the vertices of set S from G+− gives 3K1. Hence, m(G+− − S) = 1. The value of |S| + m(G+− − S) is minimum for the selected subset S. Therefore, I(G+−) = n + m−2.. Corolary 4.4. The integrity of (i) path Pn, I(P++n ) = I(P+−n ) = 2n−3, (ii) cycle Cn, I(C++n ) = I(C+−n ) = 2n−2, (iii) complete graph Kn, I(K++n ) = I(K+−n ) = n(n+1) 2 −2, (iv) complete bipartite graph Ka,b, I(K ++ a,b ) = I(K +− a,b ) = a + b + ab−2, (v) star K1,b, I(K ++ 1,b ) = I(K +− 1,b ) = 2b−1, (vi) wheel Wn, I(W++n ) = I(W+−n ) = 3n−4. The Table 4 shows integrity of basic graphs and integrity of transformation graphs G++ and G+− of graphs with same structure. G I(G) G++ and G+− I(G++) = I(G+−) P4 3 P ++ 3 and P +− 3 3 P5 3 P ++ 5 and P +− 5 7 C5 4 C ++ 3 and C +− 3 4 C6 4 C ++ 6 and C +− 6 10 Kn n K++n and K+−n n(n+1) 2 −2 K8,8 9 K ++ 2,3 and K +− 2,3 9 K8,9 9 K ++ 8,9 and K +− 8,9 87 K1,b 2 K ++ 1,b and K +− 1,b 2b−1 W27 11 W ++ 5 and W +− 5 11 W28 11 W ++ 28 and W +− 28 80 Table 4: 38 Integrity of generalized transformation graphs Theorem 4.15. For any connected graph G of order n and size m, I(G−+) = min{n + m−1,m + I(G)}. Proof. For a connected graph G of order n and size m, G−+ has order n + m. Let S1 ⊂ V (G−+). Choose a set S1 containing the edges of G. So, |S1| = |E(G)| = m. The removal of elements of set S1 from a graph G−+ gives a graph G. Consider the value |S1|+ I(G) = m + I(G). Choose a set S2 ⊂ V (G−+) consisting of all the elements of G−+ except an edge and two incident vertices. So, |S2| = n + m − 3. The removal of elements of set S2 from G−+ gives K2 ∪ K1. Hence, m(G−+ − S2) = 2. Consider, |S2| + m(G−+ −S2) = n + m−1. The minimum value among m + I(G) and n + m − 1 gives integrity of G−+. Therefore, I(G−+) = min{n + m−1,m + I(G)}. Corolary 4.5. The integrity of (i) path Pn(n ≥ 3), I(P−+n ) = n +d2 √ n + 1e−3, (ii) cycle Cn(n ≥ 4), I(C−+n ) = n + 2dne−1, (iii) complete graph Kn, I(K−+n ) = n(n+1) 2 −1, (iv) complete bipartite graph Ka,b(a,b ≥ 2), I(K−+a,b ) = ab + 1 + min{a,b}, (v) star K1,b(b ≥ 2), I(K−+1,b ) = b + 2, (vi) wheel Wn(n ≥ 5), I(W−+n ) = 2n +d2 √ n−1e−2. The column 2 and 4 Table 5 shows integrity of basic graphs and integrity of transformation graphs G−+ of graphs with same structure. Theorem 4.16. For any connected graph G of order n and size m, I(G−−) = m + I(G). Proof. Let G be an (n,m) graph. Then G−− is a graph of order n + m. Let S1 ⊂ V (G−−). Consider a set S1 containing all the edges of G. So, |S| = |E| = m. The removal of the vertices of set S1 from G−− gives a graph G. Therefore, I(G−−) = m + I(G). Corolary 4.6. The integrity of (i) path Pn, I(P−−n ) = n−3 + d2 √ n + 1e, 39 Bommanahal Basavanagoud, Shruti Policepatil G I(G) G−+ I(G−+) G−− I(G−−) P6 4 P −+ 3 4 P −− 3 4 P7 4 P −+ 7 10 P −− 7 10 C13 7 C −+ 4 6 C −− 4 7 C14 7 C −+ 14 21 C −− 14 21 Kn n K−+n n(n+1) 2 −1 K−−n n(n+1) 2 K8,9 9 K −+ 2,3 9 K −− 2,3 9 K9,9 9 K −+ 9,9 91 K −− 9,9 91 K1,b 2 K −+ 1,b b + 2 K −− 1,b 2b + 1 W32 12 W −+ 5 12 W −− 5 12 W33 12 W −+ 33 76 W −− 33 76 Table 5: (ii) cycle Cn, I(C−−n ) = n−1 + d2 √ ne, (iii) complete graph Kn, I(K−−n ) = n(n+1) 2 , (iv) complete bipartite graph Ka,b, I(K −− a,b ) = ab + 1 + min{a,b}, (v) star K1,b, I(K −− 1,b ) = 2b + 1, (vi) wheel Wn, I(W−−n ) = 2n−2 + d2 √ n−1e. The column 2 and 6 of Table 5 shows integrity of basic graphs and integrity of transformation graphs G−− of graphs with same structure. 4.2 Integrity of semitotal point graph of combination of basic graphs Definition 4.1. [16] The product G × H of two graphs G and H is defined as follows: Consider any two points u = (u1,u2) and v = (v1,v2) in V = (V1,V2). Then u and v are adjacent in G×H whenever [u1 = v1 and u2 adj v2] or [u2 = v2 and u1 adj v1]. If G and H are (n1,m1) and (n2,m2) graphs respectively. Then, G × H is (n1n2,n1m2 + n2m1) graph. 40 Integrity of generalized transformation graphs Theorem 4.17. For a graph K2 ×Pn (n ≥ 3), I ( (K2 ×Pn)++ ) =   7, if n = 3, 11, if n = 5, 5n−7 2 , if n is odd and n ≥ 7, 5n−2 2 , if n is even. Proof. The graph (K2 ×Pn)++ has 5n−2 vertices and 3(3n−2) edges. Let S ⊂ V ( (K2 ×Pn)++ ) . The proof includes the following cases. Case 1. Suppose n is odd and n ≥ 7. Choose a set S containing the two internal vertices adjacent to corresponding central vertices of each of two Pn’s in K2 × Pn. So, |S| = 4. The deletion of vertices of set S from (K2 ×Pn)++ results in a graph with components of orders 1, 7, 5(n−3) 2 . Hence, m ( (K2 × Pn)++ − S ) = 5(n−3) 2 , since n ≥ 7. The value of |S|+ m ( (K2 ×Pn)++ −S ) for this set S is 5n−7 2 and it is minimum. Therefore, I ( (K2 ×Pn)++ ) = 5n−7 2 . Case 2. Suppose n is even. Let S be a set containing the two internal vertices which are central vertices of each of two Pn’s in K2 ×Pn. So, |S| = 4. The removal of vertices of set S from (K2 × Pn)++ results in a graph with components of orders 1, 5(n−2)2 . Hence, we can write m ( (K2×Pn)++−S ) = 5(n−2) 2 . The value of |S|+m ( (K2×Pn)++−S ) for the above set S is minimum. Therefore, I ( (K2 ×Pn)++ ) = 5n−2 2 . Case 3. Suppose n = 3,5. By direct calculation using the definition of integrity, the result follows. Theorem 4.18. For a graph K2 ×Cn (n ≥ 4), I ( (K2 ×Cn)++ ) =   2 ⌈ n 2 ⌉ + 7, if n is even, 2 ⌈ n 2 ⌉ + 7, if n is odd and n ≤ 7, 2 ⌈ n 3 ⌉ + 12, if n is odd and n ≥ 9. Proof. The graph (K2 ×Cn)++ has 5n vertices and 9n edges. Let S ⊂ V ( (K2 ×Cn)++ ) . Case 1. Suppose n is even. Let S1 be an independent set of vertices of Cn such that |S1| = β0(Cn) = n2 . Case 2. Suppose n is odd. Let S′ be an independent set Cn such that |S′| = β0(Cn) = n−12 . Let v1 be a vertex of V (Cn) \ S′ such that v1 is adjacent to a vertex of S′ as well as to a vertex of V (Cn)\S′. Let S1 = S′ ∪{v1}. Combining the above two cases we get, S1 = ⌈ n 2 ⌉ . Choose a set S consisting of vertices of two Cn’s of K2 ×Cn such that |S| = 2|S1| = 2 ⌈ n 2 ⌉ . The removal of 41 Bommanahal Basavanagoud, Shruti Policepatil vertices of set S from (K2 ×Cn)++ results in a graph with components of orders 1, 7. Hence, m ( (K2×Cn)++−S ) = 7. The value of |S|+m ( (K2×Cn)++−S ) for the above set S is minimum. Therefore, I((K2 ×Cn)++) = 2 ⌈ n 2 ⌉ + 7. Case 3. Suppose n(≥ 9) is odd. Let S be an independent set of vertices of two Cn’s in a manner that the distance between the selected vertices is 3. Then, |S| = 2 ⌈ n 3 ⌉ . The removal of vertices of set S from (K2 × Cn)++ results in a disconnected graph with components of orders 1, 12. Hence, m ( (K2 ×Cn)++ −S ) = 12. Therefore, I ( (K2 ×Cn)++ ) = 2 ⌈ n 3 ⌉ + 12. Theorem 4.19. For a graph K2 ×K1,b (b ≥ 2), I ( (K2 ×K1,b)++ ) = 7. Proof. The semitotal point graph (K2×K1,b)++ has 5b+3 vertices and 3(3b+1) edges. Let S be a subset of V ( (K2 × K1,b)++ ) . Choose S such that it contains the two vertices corresponding to central vertices of each of two stars of K2 × K1,b. Clearly, |S| = 2. The removal of vertices of S from (K2 × K1,b)++ results in a graph with components of orders 1, 5. Hence, m ( (K2×K1,b)++−S ) = 5. This set S gives least value of |S|+m ( (K2×K1,b)++−S ) . Therefore, I ( (K2×K1,b)++ ) = 7. Theorem 4.20. For a graph Kp ×Kq (p = q ≥ 2), I ( (Kp ×Kq)++ ) = pq + 1. Proof. The semitotal point graph (Kp×Kq)++ has pq(p+q)2 vertices and 3pq(p+q−2) 2 edges. Select a set S such that the elements of it correspond to all the vertices of Kp×Kq. So, |S| = pq. The removal of vertices of S from (Kp ×Kq)++ results in a totally disconnected graph with 3pq(p+q−2) 2 vertices. Clearly, m ( (Kp ×Kq)++ −S ) = 1. Therefore, I ( (Kp ×Kq)++ ) = pq + 1. Definition 4.2. [16] The corona G ◦ H of graphs G and H is a graph obtained from G and H by taking one copy of G and |V (G)| copies of H and then joining by an edge each vertex of the i’th copy of H is named (H,i) with the i’th vertex of G. If G and H are (n1,m1) and (n2,m2) graphs respectively. Then, G◦H is (n1(1 + n2),m1 + n1m2 + n1n2) graph. 42 Integrity of generalized transformation graphs Theorem 4.21. For a graph K2 ◦Pn (n ≥ 3), I ( (K2 ◦Pn)++ ) =   7, if n = 3, 10, if n = 5, 3(n+1) 2 , if n is odd and n ≥ 7, 3(n 2 + 1), if n is even. Proof. The graph (K2 ◦Pn)++ has 6n + 1 vertices and 3(4n−1) edges. Let S ⊂ V ( (K2 ◦Pn)++ ) . The proof includes the following cases. Case 1. Suppose n is odd and n ≥ 7. Choose a set S containing the two internal vertices adjacent to corresponding central vertices of each of two Pn’s and the two vertices of K2 in K2 ◦ Pn. So, |S| = 6. The removal of vertices of S results in a graph with components of orders 1, 4, 3(n−1) 2 . Hence, m ( (K2 ◦ Pn)++ − S ) = 3(n−1) 2 , since n ≥ 7. The value of |S| + m ( (K2 ◦ Pn)++ − S ) for this set S is 5n−7 2 is least. Therefore, I ( (K2 ◦Pn)++ ) = 5n−7 2 . Case 2. Suppose n is even. Choose a set S containing the two internal vertices which are central vertices of each of two Pn’s and the two vertices of K2 in K2 ◦ Pn. So, |S| = 6. The removal of vertices of S from (K2 ◦ Pn)++ results in a graph with components of orders 1, 3(n−2) 2 . Clearly, we can write m ( (K2 ◦ Pn)++ − S ) = 3(n−2) 2 . The value of |S| + m ( (K2 ◦Pn)++ −S ) for the above set S is minimum. Therefore, I ( (K2 ◦Pn)++ ) = 3(n 2 + 1). Case 3. Suppose n = 3,5. By direct calculation using the definition of integrity, we can obtain the result. Theorem 4.22. For a graph K2 ◦Cn (n ≥ 4), I ( (K2 ◦Cn)++ ) = 2 ⌈n 2 ⌉ + 6. Proof. The graph (K2 ◦Cn)++ has 7n + 2 vertices and 15n edges. Let S ⊂ V ( (K2 ◦Cn)++ ) . Case 1. Suppose n is even. Let S1 be an independent set of vertices of Cn such that |S1| = β0(Cn) = n2 . Case 2. Suppose n is odd. Let S′ be an independent set of vertices of Cn such that |S′| = β0(Cn) = n−12 . Let v1 be a vertex of V (Cn)\S′ such that v1 is adjacent to a vertex of S′ as well as to a vertex of V (Cn)\S′. Let S1 = S′ ∪{v1} and |S1| = n+12 . Combining the above two cases we get, S1 = ⌈ n 2 ⌉ . Choose a set S2 consisting of vertices of two Cn’s of K2 ◦ Cn such that |S2| = 2|S1| = 2dn2e. Select a set S3 consisting of the vertices of K2 of K2 ◦ Cn. So, S = S2 ∪ S3. Hence, 43 Bommanahal Basavanagoud, Shruti Policepatil |S| = 2 ⌈ n 2 ⌉ + 2. The removal of vertices of set S from (K2 ◦Cn)++ results in a graph with components of orders 1, 4. Hence, m ( (K2 ◦ Cn)++ − S ) = 4. The value of |S| + m ( (K2 ◦Cn)++ −S ) for the above set S is minimum. Therefore, I ( (K2 ◦Cn)++ ) = 2 ⌈ n 2 ⌉ + 6. Theorem 4.23. For a graph Kp ◦Kq, I ( (Kp ◦Kq)++ ) = pq + p + 1. Proof. The semitotal point graph of Kp◦Kq has p(q+1) vertices and p2[p+q(q+ 1)−1] edges. Let S be a subset of V ( (Kp◦Kq)++ ) . Choose S such that it contains vertices of Kp and vertices of p copies of Kq of Kp ◦Kq. So |S| = p(q + 1). The removal of vertices of set S from (Kp ◦ Kq)++ results in a totally disconnected graph with p 2 [p + q(q + 1) − 1] vertices. Clearly, m ( (Kp ◦ Kq)++ − S ) = 1. Therefore, I ( (Kp ◦Kq)++ ) = pq + p + 1. 5 Conclusion In this paper, we have computed the integrity of generalized transformation graphs in terms of elements of a graph G. Also, integrity of semitotal point graph of combinations of basic graphs are obtained. Finally, we have established the relation between integrity of basic graphs and integrity of their generalized trans- formation graphs. We conclude that integrity of generalized transformation graphs are greater than or equal to integrity of graphs that have same structure. 6 Acknowledgement ∗This work is partially supported by the University Grants Commission (UGC), New Delhi, through UGC-SAP DRS-III for 2016-2021: F.510/3/DRS-III/2016(SAP- I). References [1] M. Atici and R. Crawford, The integrity of small cage graphs, Australas. J. Combin., 43, 2009, 39–55. [2] 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. 44 Integrity of generalized transformation graphs [3] M. Atici, R. Crawford and C. Ernst, New upper bounds for the integrity of cubic graphs, Int. J. Comput. Math., 81(11), 2004, 1341–1348. [4] A. Aytaç and S. Çelik, Vulnerability: Integrity of a middle graph, Selcuk J. Appl. Math., 9(1), 2008, 49–60. [5] 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. [6] C. A. Barefoot, R. Entringer and H. C. Swart, Vulnerability in graphs - A comparitive survey, J. Combin. Math. Combin. Comput., 1, 1987, 13–21. [7] C. A. Barefoot, R. Entringer and H. C. Swart, Integrity of trees and powers of cycles, Congr. Numer., 58, 1987, 103–114. [8] B. Basavanagoud, I. Gutman and C. S. Gali, Second Zagreb index and coin- dex of some derived graphs, Kragujevac J. Sci., 37, 2015, 113–121. [9] B. Basavanagoud, I. Gutman and V. R. Desai, Zagreb indices of generalized transformation graphs and their complements, Kragujevac J. Sci., 37, 2015, 99–112. [10] B. Basavanagoud, S. M. Hosamani and S. H. Malghan, Domination in semi- total point graph, J. Comp. Math. Sci., 1(5), 2010, 598–605. [11] B. Basavanagoud, S. Policepatil and P. Jakkannavar, Integrity of graph oper- ations, Trans. Comb., 10(3), 2021, 171-185. [12] P. Dündar and A. Aytac, Integrity of total graphs via certain parameters, Math. Notes, 76(5), 2004, 665–672. [13] W. Goddard, On the Vulnerability of Graphs, Ph. D. Thesis, University of Natal, Durban, S.A., 1989. [14] W. D. Goddard and H. C. Swart, On the integrity of combinations of graphs, J. Combin. Math. Combin. Comp., 4, 1988, 3–18. [15] W. Goddard and H. C. Swart, Integrity in graphs: Bounds and basics, J. Combin. Math. Combin. Comp., 7, 1990, 139–151. [16] F. Harary, Graph Theory, Addison-Wesely, Reading Mass, 1969. [17] V. R. Kulli, College Graph Theory, Vishwa Int. Publ., Gulbarga, India, 2012. 45 Bommanahal Basavanagoud, Shruti Policepatil [18] H. S. Ramane, B. Basavanagoud and R. B. Jummannavar, Harmonic index and Randic index of generalized transformation graphs, J. Nigerian Math. Soc., 37(2), 2018, 57–69. [19] E. Sampathkumar and S. B. Chikkodimath, Semitotal graphs of a graph, J. Karnatak Univ. Sci., 18, 1973, 274–280. [20] A. Vince, The integrity of a cubic graph, Discrete Appl. Math., 140, 2004, 223–239. 46