B. Basavanagoud, Praveen Jakkannavar, Shruti Policepatil

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

b.basavanagoud@gmail.com, jpraveen021@gmail.com, shrutipatil300@gmail.com

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, 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: vulnerability, connectivity, integrity, total transformation graphs

Mathematics Subject Classification: 05C40, 90C35

DOI: 10.5614/ejgta.2021.9.2.6

Received: 20 February 2020, Revised: 12 February 2021, Accepted: 26 March 2021.

1. Introduction

The vulnerability measures resistance of the network to disruption in operation after the failure of certain stations or communication links. The stability of communication network is of prime importance to designers. As network starts losing links or nodes, ultimately there is a loss in its efficiency. Thus, communication networks must be assembled to be as stable as possible, not only with respect to the initial interruption, but also with respect to the possible reconstruction of the network. A communication network can be represented as an undirected graph. Tree, mesh, hypercube and star graphs are popular communication networks. In communication networks, greater degrees of stability or less vulnerability is required. If we model a network through graph, then there are many graph-theoretic parameters to describe the stability of communication networks. Most notably, the vertex-connectivity and edge-connectivity have been frequently used. The best known measure of reliability of a graph is its vertex-connectivity κ(G) defined to be the minimum number of vertices whose removal results in a disconnected or trivial graph. The difficulty with these parameters is that they do not consider what remains after the graph is disconnected. Consequently, a number of other parameters have recently been introduced in order to overcome this difficulty. The connectivity of the two different graphs may be same, but the orders of their largest components need not be same. That is, they may differ with respect to stability. Now, the question is, how can this property be measured? In order to answer this question, the concept of integrity came into existence, which is different from connectivity. A significant area of interest and research is that of networks robustness, which aims to explore to what extent a network keeps working when failures occur in its structure and how disruptions can be avoided. Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks. An important aspect of failures in many networks is that a single failure in one node might induce failures in neighboring nodes. When a small number of failures induces more failures, resulting in a large number of failures relative to the network size. For more details on network robustness refer [30, 31, 32]. The robustness refers to the ability of surviving which considers all components remaining after random failures or intentional attacks while the integrity refers to the ability of surviving which considers the maximum component remaining after random failures or intentional attacks. The random failures cause a damage in the communication between the nodes of the complex network. Therefore, we need to consider the maximum component of the network in which still communication is possible. This can be studied using integrity.

The integrity of a graph I(G) is introduced as a measure of graph invulnerability and is defined as

\[I(G) = \min_{S \subset V(G)} \{ |S| + m(G - S) \},\\]

where m(G−S) denotes the order of a largest component of G−S. This concept was introduced by Barefoot et al. in [7], who discovered many of the early results on the subject [4, 5, 7, 8, 19, 20, 21].

Let G be a finite graph with n vertices and m edges, and it is called an (n, m) graph. We denote vertex set and edge set of graph G as V (G) and E(G), respectively. In this paper, we consider nontrivial finite undirected graph with no loops and no multiple edges. We denote Pn, Cn, Kn, Ka,b, K1,n and W1,n for a path, a cycle, a complete graph, a complete bipartite graph, a star and a wheel, respectively. The symbol ⌈x⌉ denotes the smallest integer that is greater than or equal to

x, ⌊x⌋ denotes the greatest integer that is smaller than or equal to x and the absolute value of x is denoted by |x|. For undefined graph theoretic terminologies and notations refer [16, 22, 27].

It is fact that, increase in the integrity of a graph increases the stability of the network associated with it. In literature, authors [2, 3, 8, 11, 12, 18, 25, 33] have studied the integrity of several transformation graphs. Now a question arises, how can we construct a communication network which becomes more stable than the earlier one? To answer this, we obtain the integrity of total transformation graphs from which one can compare the stability of the network with that of the network after reconstruction using the definition of the total transformation graphs. Total transformation graphs constitute a large class of graphs which are widely used in system ranging from large computers to small embedded systems on a chip. Therefore, we are interested to find integrity of total transformation graphs.

2. Preliminaries

Graph transformations have recieved the most attension. The operation of forming the graph transformations of a graph is probably the most interesting operation by which one graph is obtained from another. The complement, the k-th power of a graph, line graph, middle graph and total graph are some examples of graph transformations.

The complement G of a graph G is a graph whose vertex set is V (G) and two vertices of G are adjacent if and only if they are nonadjacent in G. The line graph [22] L(G) of a graph G is a graph with vertex set which is one to one correspondence with the edge set of G and two vertices of L(G). Jump graph [17] J(G) of a graph G is a graph whose vertices are the edges of G and two vertices of J(G) are adjacent if and only if they are nonadjacent edges of G. Evidently the jump graph J(G) of G is complement of the line graph L(G) of G. The subdivision graph [22] S(G) of a graph G is a graph with the vertex set V (S(G)) = V (G) ∪ E(G) and two vertices of S(G) are adjacent whenever they are incident in G. The partial complement of subdivision graph [24] S(G) of a graph G is a graph with the vertex set V (S(G)) = V (G) ∪ E(G) and two vertices of S(G) are adjacent whenever they are nonincident in G. For an integer k ≥ 1, the power graph G^k (the k-th power of a graph G) is defined as follows: V (G) = V (G^k ). Two distinct vertices u and v are adjacent in G^k if and only if the distance between the vertices u and v in G is atmost k. The second power of a graph is also called its square.

The total graph T(G) [22] is a graph with vertex set V (G) ∪ E(G) and two vertices of T(G) are adjacent whenever they are adjacent or incident in G. For more details on total transformation graphs one can refer to [1, 13, 14, 16, 25]. Inspired by the definition of total graph Wu and Meng defined the total transformation graphs in [6].

Definition 1. [6] Let G = (V (G), E(G)) be a graph, and x, y, z be three variables taking values + or −. The transformation graph Gxyz is the graph having the vertex set V (Gxyz) = V (G)∪E(G), and for u, v ∈ V (Gxyz), u and v are adjacent in Gxyz if and only if one of the following holds:

• (a) u, v ∈ V (G). u and v are adjacent in Gxyz if x = +; u and v are not adjacent in Gxyz if x = −.
• (b) u, v ∈ E(G). u and v are adjacent in Gxyz if y = +; u and v are not adjacent in Gxyz if y = −.

(c) \(u \in V(G), v \in E(G)\). u and v are incident in \(G^{xyz}\) if z = +; u and v are not incident in \(G^{xyz}\) if z = -.

The vertex of \(G^{xyz}\) corresponding to a vertex of G is referred to as point vertex and vertex of \(G^{xyz}\) corresponding to an edge of G is referred to as line vertex. The authors in [6] obtained eight transformation graphs, in which \(G^{+++}\) is the total graph of G, and \(G^{---}\) is its complement, similarly the graph \(G^{-++}\) is the quasi-total graph of G and \(G^{+--}\) is its complement. Also, \(G^{--+}\) and \(G^{-+-}\) are the complements of \(G^{++-}\) and \(G^{+-+}\), respectively. The total transformation graphs of the graph G are depicted in the Figure 1. In Figure 1, the circles denote the vertices of G while squares denote the edges of G.

Figure 1. The graph G and its total transformation graphs.

The following Theorems are useful in proving our results.

Theorem 2.1. [4] The integrity of

• (a) complete graph \(K_n\) is \(I(K_n) = n\),
• (b) the null graph is \(I(\overline{K_n}) = 1\),
• (c) the star is \(I(K_{1,n}) = 2\),
• (d) the path is \(I(P_n) = \lceil 2\sqrt{n+1} \rceil 2\),
• (e) the cycle is \(I(C_n) = \lceil 2\sqrt{n} \rceil 1\),
• (f) the complete bipartite graph is \(I(K_{a,b}) = 1 + \min\{a, b\}\).

Theorem 2.2. [15] The total graph T(G) is isomorphic to the square of the subdivision graph S(G).

Theorem 2.3. [8] For \[1 \le k \le \frac{n}{2}\], let \(s = \left\lceil \sqrt{\frac{n}{k} + \frac{1}{4}} - \frac{1}{2} \right\rceil\). Then

\[I(C_n^k) = k(s-1) + \left\lceil \frac{n}{s} \right\rceil.\]

3. Integrity of total transformation graphs

In this section, we obtain the integrity of total transformation graphs of some specific class of graphs.

Theorem 3.1. [33] Let \(P_n\) be a path graph with n vertices. Then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

where \[\underline{w} = \left| \sqrt{\frac{2n+1}{2}} \right|, \overline{w} = \left\lceil \sqrt{\frac{2n+1}{2}} \right\rceil\].

Theorem 3.2. [33] Let \(C_n\) be a cycle graph with n vertices. Then

\[I(C_n^{+++}) = 2\left[\sqrt{n+\frac{1}{4}} - \frac{3}{2}\right] + \left[\frac{2n}{\left[\sqrt{n+\frac{1}{4}} - \frac{1}{2}\right]}\right].\]

The expression given in Theorem 3.2 contains an error. Its correct version is given in the following theorem.

Theorem 3.3. Let \(C_n\) be a cycle graph with n vertices. Then

\[I(C_n^{+++}) = 2\left(\left\lceil \sqrt{n + \frac{1}{4}} - \frac{1}{2} \right\rceil - 1\right) + \left\lceil \frac{2n}{\left\lceil \sqrt{n + \frac{1}{4}} - \frac{1}{2} \right\rceil} \right\rceil.\]

Proof. Using the definition of subdivision graph, we have \(S(C_n) = C_{2n}\). Now from Theorem 2.2, we have \(C_n^{+++} \cong C_{2n}^2\). By Theorem 2.3, we get

\[I(C_n^{+++}) = I(C_{2n}^2) = 2\left(\left\lceil \sqrt{n + \frac{1}{4}} - \frac{1}{2} \right\rceil - 1\right) + \left\lceil \frac{2n}{\left\lceil \sqrt{n + \frac{1}{4}} - \frac{1}{2} \right\rceil} \right\rceil.\]

Theorem 3.4. Let \(K_n\) be a complete graph with n vertices. Then

\[I(K_n^{+++}) = n + I(L(K_n)).\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{+++}\) is \(n+\frac{n(n-1)}{2}\). If we consider \(S=V(K_n)\), then |S|=n and \(K_n^{+++}-S=L(K_n)\). Thus, \(I(K_n^{+++})=n+I(L(K_n))\).

Theorem 3.5. Let \(K_{a,b}(a \le b \text{ and } a, b \ge 2)\) be a complete bipartite graph. Then

\[I(K_{a,b}^{+++}) = ab + a + 1.\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{+++}\) is a+b+ab. If we consider \(S=E(K_{a,b})\), then \(S\subset V(K_{a,b}^{+++})\) with |S|=ab. If the members of S are removed from \(K_{a,b}^{+++}\), then we get \(K_{a,b}\). Therefore, \(m(K_{a,b}^{+++}-S)=a+1\). Thus, \(I(K_{a,b}^{+++})=ab+a+1\). \(\square\)

Theorem 3.6. Let \(W_{1,n} (n \ge 3)\) be a wheel graph with n + 1 vertices. Then

\[I(W_{1,n}^{+++}) = n + 1 + I(C_n^{+++}).\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{+++}\) is 3n+1. If we consider \(S=V_I\cup E_I\), where the set \(V_I\subset V\) \((W_{1,n})\) containing central vertex of \(W_{1,n}\) and \(E_I\subset E\) \((W_{1,n})\) having edges which are incident to the central vertex of \(W_{1,n}\). Then \(S\subset V\) \((W_{1,n}^{+++})\) with |S|=1+n, where \(|V_I|=1\), \(|E_I|=n\). If the members of S are removed from \(W_{1,n}^{+++}\), then we get \(C_n^{+++}\). Thus, I \((W_{1,n}^{+++})=n+1+I\) \((C_n^{+++})\).

Theorem 3.7. Let G be any connected graph with n vertices and m edges. Then

\[I(G^{---}) \le min\{m + I(\overline{G}), n + I(J(G)), n + m - 2\}.\]

Proof. Suppose we consider S = E(G). Then, \(S \subset E(G^{---})\) with |S| = m. If the members of S are removed from \(G^{---}\), then we get G. Thus, \(I(G^{---}) \leq m + I(\overline{G})\).

If we consider S = V(G). Then \(S \subset V(G^{---})\) with |S| = n. If the members of S are removed from \(G^{---}\), then \(m(G^{---} - S) = J(G)\). Thus, \(I(G^{---}) \le n + I(J(G))\).

Let \(V_I \subset V(G)\) and \(|V_I| = n - 2\). The set \(V_I\) contains all the vertices of G except two nonadjacent vertices of G. That is \(v_i, v_j \notin E(G)\). Let \(E_I \subset E(G)\) and \(|V_I| = m - 2\). The set \(E_I\) contains all the edges of G except two nonadjacent edges \(e_i, e_j\) of G in which one is adjacent to \(v_i\) but not to

\(v_j\) while the other is adjacent to \(v_j\) but not to \(v_i\). That is \(e_i, e_j \notin E(J(G))\). Let \(S_I = V_I \cup E_I\) and \(|S_I| = n + m - 4\). If we remove S vertices from \(G^{---}\), then we get components each of which is \(K_2\). Thus, \(I(G^{---}) \le n + m - 2\).

From the above cases, we conclude that

\[I(G^{---}) < min\{m + I(\overline{G}, n + I(J(G)), n + m - 2\}.\]

Theorem 3.8. Let \(P_n\) be a path graph with n vertices. Then

\[I(P_n^{---}) = \begin{cases} 1, & if \ n = 2, \\ 2n - 3, & otherwise. \end{cases}\]

Proof. If n=2, then \(P_2^{---}\) is \(\overline{K_3}\). Therefore, \(I(P_2^{---})=1\).

Let \(S_I = V_I \cup E_I\) and \(|S_I| = 2n - 5\), where \(|V_I| = n - 2\), \(|E_I| = n - 3\). The set \(V_I \subset V(P_n)\) and contains both terminal (i.e., the vertex of degree one in \(P_n\)) vertices of \(P_n\) such that \(V(P_n) \setminus V_I\) contains two adjacent vertices of \(P_n\) say u, v and one of them is adjacent to the terminal vertex of the path, while the set \(E_I \subset E(P_n)\) is chosen in such a way that, it must not contain the edge uv and one of the two edges which are adjacent to the edge uv. Then clearly, \(S_I\) will form a subset of \(V(P_n^{---})\) such that

\[|S_I| + m(P_n^{---} - S_I) = \min_{S \subset V(P_n^{---})} \{|S| + m(P_n^{---} - S)\},\]

where \(m(P_n^{---} - S_I) = 2\).

Thus,

\[I(P_n^{---}) = |S_I| + m(P_n^{---} - S_I) = 2n - 3.\]

Theorem 3.9. Let \(C_n\) be a cycle graph with \(n \geq 3\) vertices. Then

\[I(C_n^{---}) = \begin{cases} 2, & if \ n = 3, \\ 2(n-1), & otherwise. \end{cases}\]

Proof. Case 1. Suppose n=3, \(C_3^{---}\) is a disconnected graph. If we choose no vertices in set S, then \(m(C_n^{---}-S)=2\). Thus, \(I(C_3^{---})=2\).

Case 2. If \(n \ge 4\), then \(S_I = V_I \cup E_I\) and \(|S_I| = 2n - 4\), where \(|V_I| = n - 2\) and \(|E_I| = n - 2\). The set \(V_I \subset V(C_n)\) such that \(V(C_n) \setminus V_I\) contains two adjacent vertices of \(C_n\) say u and v, while the set \(E_I \subset E(C_n)\) is chosen in such a way that, it contains the edge uv and one of the two edges which are adjacent to it in \(C_n\). Then clearly, \(S_I\) will form a subset of \(V(C_n^{---})\) such that

\[|S_I| + m(C_n^{---} - S_I) = \min_{S \subset V(C_n^{---})} \{|S| + m(C_n^{---} - S)\},\]

where \(m(C_n^{---} - S_I) = 2\).

Thus,

\[I(C_n^{---}) = 2(n-1).\]

Theorem 3.10. Let \(K_n\) be a complete graph with n vertices. Then

\[I(K_n^{---}) = \begin{cases} 2, & if \ n = 3, \\ n + I(J(K_n)), & otherwise. \end{cases}\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{---}\) is \(n + \frac{n(n-1)}{2}\).

Case 1. Suppose n=3, then \(K_3\cong C_3\). The proof is given in Theorem 3.9.

Case 2. If \(n \ge 4\), then we choose \(S = V(K_n)\). It is clear to write |S| = n and \(K_n^{--} - S = J(K_n)\). Thus, \(I(K_n^{--}) = n + I(J(K_n))\).

Theorem 3.11. Let \(K_{1,n}(n \ge 2)\) be a star graph with n+1 vertices. Then

\[I(K_{1,n}^{---}) = n+1.\]

Proof. The number of edges in \(K_{1,n}\) is n. Therefore, the number of vertices in \(K_{1,n}^{---}\) is 2n+1. If we consider \(S=V(K_{1,n})\setminus\{u\}\), where the vertex \(\{u\}\) is the central vertex (i.e., the vertex of degree n) of the star graph, then |S|=n. If the members of S are removed from \(K_{1,n}^{---}\), then we get \(\overline{K_{n+1}}\). Thus, \(I(K_{1,n}^{---})=n+1\).

Theorem 3.12. Let \(K_{a,b}(a \le b \text{ and } a, b \ge 2)\) be a complete bipartite graph. Then

\[I(K_{ab}^{---}) = b(a+1).\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{---}\) is a+b+ab. If we consider \(S=E(K_{a,b})\), then \(S\subset V(K_{a,b}^{---})\) with |S|=ab and \(K_{a,b}^{---}-S=K_a\cup K_b\). Therefore, \(m(K_{a,b}^{---}-S)=b\). Thus, \(I(K_{a,b}^{---})=b(a+1)\).

Theorem 3.13. Let \(W_{1,n}(n \ge 3)\) be a wheel graph with n+1 vertices. Then

\[I(W_{1,n}^{---}) = 2n + 1.\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{---}\) is 3n+1. If we consider \(S=V_I\cup E_I\), then \(S\subset V(W_{1,n}^{---})\) with |S|=2n, where \(|V_I|=n\), \(|E_I|=n\). The set \(V_I=V(W_{1,n})\) and \(E_I\subset E(W_{1,n})\) such that all members of \(E_I\) should form a cycle \(C_n\) in \(W_{1,n}\). If the members of S are removed from \(W_{1,n}^{---}\), then we get \(\overline{K_n}\). Thus, \(I(W_{1,n}^{---})=2n+1\). \(\square\)

Definition 2. [29] The quasi-total graph \((G^{-++})\) of a graph G is the graph whose vertex set is \(V(G) \cup E(G)\) and the two vertices in \((G^{-++})\) are adjacent if and only if they correspond to two non-adjacent vertices of G or to two adjacent edges of G or to a vertex and an edge incident with it, in G (see Figure 1).

The results on integrity of the quasi-total graph \((G^{-++})\) of a graph can be found in [11] and the details of quasi-total graph can be found in [9, 10, 26, 29]. The following theorem gives the integrity of the complement of the quasi-total graph \((G^{+--})\) of a graph.

Theorem 3.14. Let G be any connected graph with n vertices and m edges. Then

\[I(G^{+--}) \le min\{m + I(G), n + I(J(G))\}.\]

Proof. Suppose we consider S = E(G). Then \(S \subset E(G^{+--})\) with |S| = m. If the members of S are removed from \(G^{+--}\), then we get G. Thus, \(I(G^{+--}) \leq m + I(G)\).

If we consider S = V(G), then \(S \subset V(G^{+--})\) with |S| = n and \(m(G^{+--} - S) = J(G)\). Thus, \(I(G^{+--}) \leq n + I(J(G))\).

From the above two cases, we can conclude that \(I(G^{+--}) \leq min\{m + I(G), n + I(J(G))\}\). \(\square\)

Theorem 3.15. Let \(P_n\) be a path graph with n vertices. Then

\[I(P_n^{+--}) = \begin{cases} 2, & if \ n = 2, \\ n + \lceil 2\sqrt{n+1} \rceil - 3, & otherwise. \end{cases}\]

Proof. Suppose n=2. Then \(P_2^{+--}\) is a disconnected graph with components \(K_1\) and \(K_2\). Therefore, \(I(P_2^{+--})=2\). If \(n\geq 3\), then by removing end vertices of \(P_n\) we get \(3K_1\). Thus, \(I(P_3^{+--})=3\). If we consider the set \(S_I=E(P_n)\), then clearly, \(S_I\) will form a subset of \(V(P_n^{+--})\) such that

\[|S_I| + m(P_n^{+--} - S_I) = \min_{S \subset V(P_n^{+--})} \{|S| + m(P_n^{+--} - S)\},\]

where \(m(P_n^{+--} - S_I) = P_n\). Thus,

\[I(P_n^{+--}) = |S_I| + m(P_n^{+--} - S_I) = n - 1 + I(P_n) = n + \left\lceil 2\sqrt{n+1} \right\rceil - 3.\]

Theorem 3.16. Let \(C_n\) be a cycle graph with n vertices. Then

\[I(C_n^{+--}) = \begin{cases} 4, & \text{if } n = 3, \\ 6, & \text{if } n = 4, \\ n + \lceil 2\sqrt{n} \rceil - 1, & \text{otherwise.} \end{cases}\]

Proof. If n=3, then by removing all vertices of \(C_3\) from \(C_3^{+--}\) we get \(3K_1\). Thus \(I(C_3^{+--})=4\). If n=4, then by removing all vertices of \(C_4\) from \(C_4^{+--}\) we get two components each of which is \(K_2\). Thus \(I(C_4^{+--})=6\). If we consider the set \(S_I=E(C_n)\). Then clearly, \(S_I\) will form a subset of \(V(C_n^{+--})\) such that

\[|S_I| + m(C_n^{+--} - S_I) = \min_{S \subset V(C_n^{+--})} \{|S| + m(C_n^{+--} - S)\},\]

where \(m(C_n^{+--} - S_I) = C_n\).

Thus,

\[I(C_n^{+--}) = |S_I| + m(C_n^{+--} - S_I) = n + I(C_n) = n + \lceil 2\sqrt{n} \rceil - 1.\]

Theorem 3.17. Let \(K_n\) be a complete graph with \(n(n \ge 3)\) vertices. Then

\[I(K_n^{+--}) = n + I(J(K_n)).\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{+--}\) is \(n+\frac{n(n-1)}{2}\). If we consider \(S=V(K_n)\), then |S|=n and \(K_n^{+--}-S=J(K_n)\). Thus, \(I(K_n^{+--})=n+I(J(K_n))\).

Theorem 3.18. Let \(K_{1,n}\) be a star graph with n+1 vertices. Then

\[I(K_{1,n}^{+--}) = n+1.\]

Proof. The number of edges in \(K_{1,n}\) is n. Therefore, the number of vertices in \(K_{1,n}^{+--}\) is 2n+1. If we consider \(S=(V(K_{1,n})\setminus\{u\})\) where u is the central vertex (i.e., the vertex of degree n) of \(K_{1,n}\), then |S|=n. If the members of S are removed from \(K_{1,n}^{+--}\), then we get \(\overline{K_{n+1}}\). Thus, \(I(K_{1,n}^{+--})=n+1\).

Theorem 3.19. Let \(K_{a,b}(a \le b \text{ and } a, b \ge 2)\) be a complete bipartite graph. Then

\[I(K_{a,b}^{+--}) = ab - a + b + 2\left\lfloor \frac{a}{4} \right\rfloor + \left\lceil \frac{a - \left\lfloor \frac{a}{4} \right\rfloor}{\left\lfloor \frac{a}{4} \right\rfloor + 1} \right\rceil.\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{+--}\) is a+b+ab. If we consider \(S=V(K_{a,b})\cup E_I(K_{a,b})\), then \(S\subset V(K_{a,b}^{+--})\) with \(|S|=ab-a+b+2\left\lfloor\frac{a}{4}\right\rfloor\), where \(|E_I(K_{a,b})|=2\left\lfloor\frac{a}{4}\right\rfloor-2a\) and \(E(K_{a,b})\setminus E_I(K_{a,b})\) must induce two paths of length a-1 in \(K_{a,b}^{+--}\). If the members of S are removed from \(K_{a,b}^{+--}\), then we get \(2P_a\). Therefore, \(m(K_{a,b}^{+--}-S)=\left\lceil\frac{a-\left\lfloor\frac{a}{4}\right\rfloor}{\left\lfloor\frac{a}{4}\right\rfloor+1}\right\rceil\). Hence, \(I(K_{a,b}^{+--})=ab-a+b+2\left\lfloor\frac{a}{4}\right\rfloor+\left\lceil\frac{a-\left\lfloor\frac{a}{4}\right\rfloor}{\left\lfloor\frac{a}{4}\right\rfloor+1}\right\rceil\).

Theorem 3.20. Let \(W_{1,n} (n \ge 3)\) be a wheel graph with n+1 vertices. Then

\[I(W_{1,n}^{+--}) = 2n + \lceil 2\sqrt{n} \rceil.\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{+--}\) is 3n+1. If we consider \(S=E(W_{1,n})\), then \(S\subset V(W_{1,n}^{+--})\) with |S|=2n and \(W_{1,n}^{+--}-S=W_{1,n}\). Thus, \(I(W_{1,n}^{+--})=2n+\lceil 2\sqrt{n}\rceil\).

Theorem 3.21. If G is any connected graph with \(n(n \ge 4)\) vertices and m edges, then

\[I(G^{--+}) \le \min\{n + I(J(G)), m + I(\overline{G}), n + m - 2\}.\]

Proof. Suppose we consider S=E(G). Then \(S\subset E(G^{--+})\) with |S|=m. If the members of S are removed from \(G^{--+}\), then we get \(\overline{G}\). Thus, \(I(G^{--+})\leq m+I(\overline{G})\). If we consider S=V(G), then \(S\subset V(G^{--+})\) with |S|=n and \(m(G^{--+}-S)=J(G)\). Thus, \(I(G^{--+})\leq n+I(J(G))\).

Let \(V_I \subset V(G)\) and \(|V_I| = n-2\). The set \(V_I\) contains all the vertices of G except two nonadjacent vertices of G. That is \(v_i, v_j \notin E(G)\). Let \(E_I \subset E(G)\) and \(|V_I| = m-2\). The set \(E_I\) contains all the edges of G except two nonadjacent edges \(e_i, e_j\) of G in which one is adjacent to \(v_i\) but not to \(v_j\) while the other is adjacent to \(v_j\) but not to \(v_i\). That is \(e_i, e_j \notin E(J(G))\). Let \(S_I = V_I \cup E_I\) and \(|S_I| = n + m - 4\). If we remove S vertices from \(G^{--+}\), then we get components each of which is \(K_2\). Thus, \(I(G^{--+}) \leq n + m - 2\).

From the above cases, we conclude that

\[I(G^{--+}) \le \min\{n + I(J(G)), m + I(\overline{G}), n + m - 2\}.\]

Theorem 3.22. Let \(P_n\) be a path graph with n vertices. Then

\[I(P_n^{--+}) = \begin{cases} 2, & if \ n = 2, \\ 4, & if \ n = 3, \\ 6, & if \ n = 4, \\ 2(n-2), & otherwise. \end{cases}\]

Proof. If n=2, then \(P_2^{--+}=P_3\) and \(I(P_2^{--+})=2\). If n=3, then by removing all vertices of \(P_3\) from \(P_3^{--+}\) we get two components of \(K_1\). Thus \(I(P_3^{--+})=4\). If n=4, then by removing all vertices of \(P_4\) from \(P_4^{--+}\) we get one components of \(K_2\). Thus \(I(P_4^{--+})=6\). Let \(P_n\) be a path with vertex set \(V(P_n)=\{v_1,v_2,\ldots,v_n\}\) and the edge set \(E(P_n)=\{e_1,e_2,\ldots,e_{n-1}\}\). Suppose we consider \(S_I=V_I\cup E_I\) and \(|S_I|=2n-5\), where \(|V_I|=n-2\), \(|E_I|=n-3\). The set \(V_I\subset V(P_n)\) and \(V_I=V(P_n)\setminus\{v_2,v_3\}\), while the set \(E_I\subset E(P_n)\) is chosen in such a way that, \(E_I=E(P_n)\setminus\{e_{n-2},e_{n-1}\}\). Then clearly, \(S_I\) will form a subset of \(V(P_n^{--+})\) such that

\[|S_I| + m(P_n^{--+} - S_I) = \min_{S \subset V(P_n^{--+})} \{|S| + m(P_n^{--+} - S)\},\]

where \(m(P_n^{--+} - S_I) = 1\). Thus,

\[I(P_n^{--+}) = |S_I| + m(P_n^{--+} - S_I) = 2(n-2).\]

Theorem 3.23. Let \(C_n\) be a cycle graph with n vertices. Then

\[I(C_n^{--+}) = \begin{cases} 4, & if \ n = 3, \\ 6, & if \ n = 4, \\ 2n - 3, & otherwise. \end{cases}\]

Proof. If n=3, then \(C_3^{--+}=C_6\) and \(I(C_3^{--+})=4\). If n=4, then by removing all vertices of \(C_4\) from \(C_4^{--+}\) we get three components of \(K_2\). Thus \(I(C_4^{--+})=6\).

If \(n \geq 5\), then let \(S_I = V_I \cup E_I\) and \(|S_I| = 2n - 4\), where \(|V_I| = n - 2 = |E_I|\).

The set \(V_I \subset V(C_n)\) such that \(V(C_n) \setminus V_I\) contains two adjacent vertices of \(C_n\) say u and v, while the set \(E_I \subset E(C_n)\) is chosen in such a way that, it must contain the edge uv and

\(E(C_n) \setminus E_I = \{e_i, e_j\}\), where \(e_i\) and \(e_j\) are adjacent and they are not adjacent to the edge uv in \(C_n\). Then clearly, \(S_I\) will form a subset of \(V(C_n^{--+})\) such that

\[|S_I| + m(C_n^{--+} - S_I) = \min_{S \subset V(C_n^{--+})} \{|S| + m(C_n^{--+} - S)\},\]

where \(m(C_n^{--+} - S_I) = 1\). Thus, \(I(C_n^{--+}) = 2n - 3\).

Theorem 3.24. Let \(K_n\) be a complete graph with \(n(n \ge 3)\) vertices. Then

\[I(K_n^{--+}) = n + I(J(K_n)).\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{--+}\) is \(n+\frac{n(n-1)}{2}\). If we consider \(S=V(K_n)\), then |S|=n and \(K_n^{--+}-S=J(K_n)\). Thus, \(I(K_n^{--+})=n+I(J(K_n))\).

Theorem 3.25. Let \(K_{1,n}\) be a star graph with n+1 vertices. Then

\[I(K_{1,n}^{--+}) = n + 2.\]

Proof. The number of edges in \(K_{1,n}\) is n. Therefore, the number of vertices in \(K_{1,n}^{--+}\) is 2n+1. If we consider \(S=V(K_{1,n})\), then |S|=n+1. It is clear that \(K_{1,n}^{--+}-S=\overline{K_n}\). Thus, \(I(K_{1,n}^{--+})=n+2\).

Theorem 3.26. Let \(K_{a,b}(a \le b \text{ and } a, b \ge 2)\) be a complete bipartite graph. Then

\[I(K_{a,b}^{--+}) = b(a+1).\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{--+}\) is a+b+ab. If we consider \(S=E(K_{a,b})\), then \(S\subset V(K_{a,b}^{--+})\) with |S|=ab. If the members of S are removed from \(K_{a,b}^{--+}\), then \(K_{a,b}^{--+}-S=K_a\cup K_b\). Since m(G-S) is the order of the largest component of G-S. Therefore, \(m(K_{a,b}^{--+}-S)=b\). Thus, \(I(K_{a,b}^{--+})=b(a+1)\).

Theorem 3.27. Let \(W_{1,n}(n \ge 3)\) be a wheel graph with n+1 vertices. Then

\[I(W_{1,n}^{--+}) = 2(n+1).\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{--+}\) is 3n+1. If we consider \(S=V_I\cup E_I\), then \(S\subset V(W_{1,n}^{--+})\) with |S|=2n+1, where \(V_I=V(W_{1,n})\) and \(E_I\) is the collection of all edges of the wheel graph \(W_{1,n}\), which are the edges forming the cycle \(C_n\). If the members of S are removed from \(W_{1,n}^{--+}\), then we get \(\overline{K_n}\). Thus, \(I(W_{1,n}^{--+})=2(n+1)\). \(\square\)

Theorem 3.28. If G is any connected graph with \(n(n \ge 4)\) vertices and m edges, then

\[I(G^{++-}) \le \min\{m + I(G), n + I(L(G)), n + m - 2\}.\]

Proof. Suppose we consider S = E(G). Then \(S \subset E(G^{++-})\) with |S| = m. If the members of Sare removed from \(G^{++-}\), then we get G. Thus, \(I(G^{++-}) \le m + I(G)\).

If we consider S = V(G), then \(S \subset V(G^{++-})\) with |S| = n. It is clear that \(m(G^{++-} - S) = L(G)\). Thus, \(I(G^{++-}) \le n + I(L(G))\).

Let \(V_I \subset V(G)\) and \(|V_I| = n - 2\). The set \(V_I\) contains all the vertices of G except two nonadjacent vertices of G. That is \(v_i, v_i \notin E(G)\). Let \(E_I \subset E(G)\) and \(|V_I| = m - 2\). The set \(E_I\) contains all the edges of G except two nonadjacent edges \(e_i, e_i\) of G in which one is adjacent to \(v_i\) but not to \(v_i\) while the other is adjacent to \(v_j\) but not to \(v_i\). That is \(e_i, e_j \notin E(L(G))\). Let \(S_I = V_I \cup E_I\) and \(|S_I| = n + m - 4\). If we remove S vertices from \(G^{++-}\), then we get components each of which is \(K_2\). Thus, \(I(G^{++-}) \le n + m - 2\).

From the above cases, we can conclude that

\[I(G^{++-}) \le \min\{m + I(G), n + I(L(G)), n + m - 2\}.\]

Theorem 3.29. Let \(P_n\) be a path graph with n vertices. Then

\[I(P_n^{++-}) = \begin{cases} 4, & \text{if } n = 3, \\ 5, & \text{if } n = 4, \\ 2(n-2), & \text{if } n = 5, 6, \\ \lceil 2\sqrt{n+1} \rceil + n - 3 & \text{otherwise.} \end{cases}\]

Proof. If n=3, then \(P_3^{++-}=C_5\) and \(I(P_3^{++-})=4\). If n=4, then by taking S as the collection of the two central vertices and the edge joining them in \(P_4\), we get \(I(P_4^{++-}) = 5\). If n = 5, 6, then by taking S as the collection of the central vertex(or vertices (for n=6)) and the edges incident with it (them (for n=6)) in \(P_n\), we get \(I(P_n^{++-})=2(n-2)\). Suppose \(n\geq 7\). Then let \(P_n\)be a path with vertex set \(V(P_n) = \{v_1, v_2, \dots, v_n\}\) and the edge set \(E(P_n) = \{e_1, e_2, \dots, e_{n-1}\}\). Suppose we consider \(S = E(P_n)\), then |S| = n - 1. If we remove all the members of S from \(P_n^{++-}\), then we get \(P_n\). Thus, \(I(P_n^{++-}) = |S| + I(P_n) = \lceil 2\sqrt{n+1} \rceil + n - 3\).

Thus, \[I(P_n^{++-}) = |S| + I(P_n) = |2\sqrt{n+1}| + n - 3.\]

Theorem 3.30. Let \(C_n\) be a cycle graph with n vertices. Then

\[I(C_n^{++-}) = \begin{cases} 5, & if \ n = 3, \\ 2(n-1), & if \ n = 4, 5, \\ n + \lceil 2\sqrt{n} \rceil - 1, & otherwise. \end{cases}\]

Proof. If n=3, then by taking the set S as the collection of two edges and a vertex which not incident with them in \(C_3\), we get \(I(C_3^{++-}) = 5\). If n = 4, 5, then by taking the set S as shown in Figure 2, we get \(I(C_n^{++-}) = 2(n-1)\).

Suppose \[n \ge 6\]. Then consider \(S = E(C_n)\). It is clear that \(C_n^{++-} - S = C_n\). Thus, \(I(C_n^{++-}) = |S| + I(C_n) = n + \lceil 2\sqrt{n} \rceil - 1\).

Figure 2. Choosing the set S in the graphs \(C_4^{++-}\) and \(C_5^{++-}\).

Theorem 3.31. Let \(K_n\) be a complete graph with \(n(n \ge 3)\) vertices. Then

\[I(K_n^{++-}) = \frac{n^2 + n - 2}{2}.\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{++-}\) is \(n+\frac{n(n-1)}{2}\). If we consider \(S=V_I\cup E_I\) such that \(|S|=n+\frac{n(n-1)}{2}-1\). The set \(V_I\subset V(K_n)\) and \(V(K_n)\setminus V_I=\{u,v\}\), while the set \(E_I\subset E(K_n)\) and \(E(K_n)\setminus E_I=\{uv\}\). Therefore, \(K_n^{++-}-S=K_1\cup K_2\). Thus, \(I(K_n^{++-})=\frac{n^2+n-2}{2}\).

Theorem 3.32. Let \(K_{1,n}\) be a star graph with n+1 vertices. Then

\[I(K_{1,n}^{++-}) = n+2.\]

Proof. The number of edges in \(K_{1,n}\) is n. Therefore, the number of vertices in \(K_{1,n}^{++-}\) is 2n+1. If we consider \(S = E(K_{1,n}) \cup \{u\}\) where the vertex u is the central vertex of \(K_{1,n}\), then |S| = n+1. Therefore, \(K_{1,n}^{++-} - S = \overline{K_n}\). Thus, \(I(K_{1,n}^{++-}) = n+2\).

Theorem 3.33. Let \(K_{a,b} (a \leq b \text{ and } a, b \geq 2)\) be a complete bipartite graph. Then

\[I(K_{a,b}^{++-}) = ab + a + 1.\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{++-}\) is a+b+ab. If we consider \(S=E(K_{a,b})\), then \(S\subset V(K_{a,b}^{++-})\) with |S|=ab and \(K_{a,b}^{++-}-S=K_{a,b}\). Therefore, \(m(K_{a,b}^{++-}-S)=a+1\). Thus, \(I(K_{a,b}^{++-})=ab+a+1\).

Theorem 3.34. Let \(W_{1,n} (n \ge 3)\) be a wheel graph with n+1 vertices. Then

\[I(W_{1,n}^{++-}) = 2n + \lceil 2\sqrt{n} \rceil.\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{++-}\) is 3n+1. If we consider \(S=E(W_{1,n})\), then \(S\subset V(W_{1,n}^{++-})\) with |S|=2n. If the members of S are removed from \(W_{1,n}^{++-}\), then we get \(W_{1,n}\).

Thus, \[I(W_{1,n}^{++-}) = 2n + I(W_{1,n}) = 2n + \lceil 2\sqrt{n} \rceil\].

Theorem 3.35. If G is any connected graph with n(n > 4) vertices and m edges, then

\[I(G^{-+-}) \leq \min\{n + I(L(G)), m + I(\overline{G}), n + m - 2\}.\]

Proof. Suppose we consider S=E(G). Then \(S\subset E(G^{-+-})\) with |S|=m. It is clear that \(m(G^{-+-}S)=\overline{G}\). Thus, \(I(G^{-+-})\leq m+I(\overline{G})\).

If we consider S=V(G). Then \(S\subset V(G^{-+-})\) with |S|=n and \(m(G^{-+-}-S)=L(G)\). Thus, \(I(G^{-+-})\leq n+I(L(G))\).

Let \(V_I \subset V(G)\) and \(|V_I| = n-2\). The set \(V_I\) contains all the vertices of G except two nonadjacent vertices of G. That is \(v_i, v_j \notin E(G)\). Let \(E_I \subset E(G)\) and \(|V_I| = m-2\). The set \(E_I\) contains all the edges of G except two nonadjacent edges \(e_i, e_j\) of G in which one is adjacent to \(v_i\) but not to \(v_j\) while the other is adjacent to \(v_j\) but not to \(v_i\). That is \(e_i, e_j \notin E(L(G))\). Let \(S_I = V_I \cup E_I\) and \(|S_I| = n + m - 4\). If we remove S from \(G^{-+-}\), then we get components each of which is \(K_2\). Thus, \(I(G^{-+-}) \leq n + m - 2\).

From the above cases, we conclude that

\[I(G^{-+-}) \le \min\{n + I(L(G)), m + I(\overline{G}), n + m - 2\}.\]

Theorem 3.36. Let \(P_n\) be a path graph with n vertices. Then

\[I(P_n^{-+-}) = 2n - 3.\]

Proof. Let \(P_n\) be a path with vertex set \(V(P_n) = \{v_1, v_2, \dots, v_n\}\) and the edge set \(E(P_n) = \{e_1, e_2, \dots, e_{n-1}\}\). Suppose we consider \(S_I = V_I \cup E_I\) and \(|S_I| = 2n-5\), where \(|V_I| = n-2\), \(|E_I| = n-3\). The set \(V_I \subset V(P_n)\) and \(V_I = V(P_n) \setminus \{v_2, v_3\}\), while the set \(E_I \subset E(P_n)\) is chosen in such a way that, \(E_I = E(P_n) \setminus \{e_1, e_3\}\). Then clearly, \(S_I\) will form a subset of \(V(P_n^{-+-})\) such that

\[|S_I| + m(P_n^{-+-} - S_I) = \min_{S \subset V(P_n^{-+-})} \{|S| + m(P_n^{-+-} - S)\},\]

where \(m(P_n^{-+-} - S_I) = 2\).

Thus,

\[I(P_n^{-+-}) = |S_I| + m(P_n^{-+-} - S_I) = 2n - 3.\]

Theorem 3.37. Let \(C_n\) be a cycle graph with \(n(n \ge 3)\) vertices. Then

\[I(C_n^{-+-}) = 2(n-1).\]

Proof. If \(n \geq 3\), then let \(S_I = V_I \cup E_I\) and \(|S_I| = 2n-4\), where \(|V_I| = n-2 = |E_I|\). The set \(V_I \subset V(C_n)\) such that \(V(C_n) \setminus V_I\) contains two adjacent vertices of \(C_n\) say u and v, while the set \(E_I \subset E(C_n)\) is chosen in such a way that, it must contain the edge uv and \(E(C_n) \setminus E_I\) must contain two edges adjacent with uv in \(C_n\). Then clearly, \(S_I\) will form a subset of \(V(C_n^{-+-})\) such that

\[|S_I| + m(C_n^{-+-} - S_I) = \min_{S \subset V(C_n^{-+-})} \{|S| + m(C_n^{-+-} - S)\},\]

where \(m(C_n^{-+-} - S_I) = 1\). Thus, \(I(C_n^{-+-}) = 2n - 3\).

Theorem 3.38. Let \(K_n\) be a complete graph with \(n(n \ge 3)\) vertices. Then

\[I(K_n^{-+-}) = \frac{n(n-1)}{2} + 1.\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{-+-}\) is \(n+\frac{n(n-1)}{2}\). If we consider \(S=E(K_n)\), then \(|S|=\frac{n(n-1)}{2}\) and \(K_n^{-+-}-S=\overline{K_n}\). Thus, \(I(K_n^{-+-})=\frac{n(n-1)}{2}+1\).

Theorem 3.39. Let \(K_{1,n}\) be a star graph with n+1 vertices. Then

\[I(K_{1,n}^{-+-}) = 2n - 1.\]

Proof. The number of edges in \(K_{1,n}\) is n. Therefore, the number of vertices in \(K_{1,n}^{-+-}\) is 2n+1. If we consider \(S=(V(K_{1,n})\setminus\{u,v\})\cup(E(K_{1,n})\setminus\{uv\})\), where the vertex u is the central vertex (i.e., the vertex of degree n) in \(K_{1,n}\), then |S|=2n-2. If the members of S are removed from \(K_{1,n}^{-+-}\), then we get \(\overline{K_3}\). Thus, \(I(K_{1,n}^{-+-})=2n-1\).

Theorem 3.40. Let \(K_{a,b}(a \le b \text{ and } a, b \ge 2)\) be a complete bipartite graph. Then

\[I(K_{a,b}^{-+-}) = b(a+1).\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{-+-}\) is a+b+ab. If we consider \(S=E(K_{a,b})\), then \(S\subset V(K_{a,b}^{-+-})\) with |S|=ab. If the members of S are removed from \(K_{a,b}^{-+-}\), then \(K_{a,b}^{-+-}-S=K_a\cup K_b\). Since m(G-S) is the order of the largest component of G-S. Therefore, \(m(K_{a,b}^{-+-}-S)=b\). Thus, \(I(K_{a,b}^{-+-})=b(a+1)\).

Theorem 3.41. Let \(W_{1,n}(n \ge 3)\) be a wheel graph with n+1 vertices. Then

\[I(W_{1,n}^{-+-}) = 2n + \lceil 2\sqrt{n} \rceil.\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{-+-}\) is 3n+1. If we consider \(S=V_I\cup E_I\), then \(S\subset V(W_{1,n}^{-+-})\) with |S|=2n+1, where \(|V_I|=V(W_{1,n})\) and \(|E_I|\) is the collection of all edges of the wheel graph \(W_{1,n}\), which are adjacent to the central vertex (i.e., the vertex of degree n). If the members of S are removed from \(W_{1,n}^{-+-}\), then we get \(\overline{K_n}\). Thus, \(I(W_{1,n}^{-+-})=2n+1+I(C_n)=2n+\lceil 2\sqrt{n}\rceil\).

Theorem 3.42. If G is any connected graph with n vertices and m edges, then

\[I(G^{+-+}) \le min\{m + I(G), n + I(J(G))\}.\]

Proof. Suppose we consider S=E(G). Then \(S\subset E(G^{+-+})\) with |S|=m and \(m(G^{+-+}-S)=G\). Thus, \(I(G^{+-+})\leq m+I(G)\). If we consider S=V(G). Then \(S\subset V(G^{+-+})\) with |S|=n. If the members of S are removed from \(G^{+-+}\), then we get J(G). Thus, \(I(G^{+-+})\leq n+I(J(G))\). From the above two cases, we can conclude that

\[I(G^{+-+}) \le min\{m + I(G), n + I(J(G))\}.\]

Theorem 3.43. Let \(P_n\) be a path graph with n vertices. Then

\[I(P_n^{+-+}) = \begin{cases} 3, & \text{if } n = 2, 3 \\ 5, & \text{if } n = 4, \\ 6, & \text{if } n = 5, \\ n+2+\left\lfloor\frac{n-6}{4}\right\rfloor, & \text{otherwise.} \end{cases}\]

Proof. If n=2, then \(P_2^{+-+}\cong C_3\), we get \(I(P_2^{+-+})=3\).

If n=3, then by taking the set S which is intermediate vertex, we get \(I(P_3^{+-+})=3\).

If n=4, then consider the set \(S_I=V_I\cup E_I\) such that \(V_I\subset V(P_n), |V_I|=2\) and it should contain intermediate vertices, while the set \(E_I\subset E(P_n), |E_I|=2\) and it should contain end vertices. So, |S|=4 and \(m(P_4^{+-+}-S)=2\). hence, we get desired result.

Let \(P_n\) be a path with vertex set \(V(P_n)=\{v_1,v_2,\ldots,v_n\}\) and the edge set \(E(P_n)=\{e_1,e_2,\ldots,e_{n-1}\}\). Suppose n=5, we consider the set \(S_I=V_I\cup E_I\) such that \(V_I\subset V(P_n), |V_I|=2\) and it should contain the vertices \(\{v_2,v_4\}\), while the set \(E_I\subset E(P_n)\) and \(E_I=\{e_1,e_3\}, |E_I|=2\). So, |S|=4 and \(m(P_4^{+-+}-S)=2\). hence, we get desired result.

Suppose \(n \geq 5\), we consider the set \(S_I = V_I \cup E_I\) such that \(V_I \subset V(P_n)\), \(|V_I| = 2 + \left\lfloor \frac{n-6}{4} \right\rfloor\) and it should not contain the vertices \(v_1, v_2, v_4, v_5\), also the distance between any two members of \(V_I\) must equals to 3, while the set \(E_I \subset E(P_n)\) and \(E(P_n) \setminus E_I = \{e_2, e_3\}, |E_I| = n-3\). Then clearly, \(S_I\) will form a subset of \(V(P_n^{+-+})\) such that

\[|S_I| + m(P_n^{+-+} - S_I) = \min_{S \subset V(P_n^{+-+})} \{|S| + m(P_n^{+-+} - S)\},\]

where \(m(P_n^{+-+} - S_I) = 3\).

Thus,

\[I(P_n^{+-+}) = |S_I| + m(P_n^{+-+} - S_I) = n + 2 + \left\lfloor \frac{n-6}{4} \right\rfloor.\]

Theorem 3.44. Let \(C_n\) be a cycle graph with n vertices. Then

\[I(C_n^{+-+}) = n + \min\{I(C_n), I(\overline{C_n})\}.\]

Proof. The cycle graph \(C_n\) has n edges. Therefore, we have two choices to choose the set S if we consider the set \(S = E(C_n)\), then \(C_n^{+-+} - S = C_n\). Suppose we choose the set \(S = V(C_n)\), then \(C_n^{+-+} - S = \overline{C_n}\). Clearly, S will form a subset of \(V(C_n^{+-+})\) such that

\[|S| + m(C_n^{+-+} - S) = \min_{S \subset V(C_n^{+-+})} \{|S| + m(C_n^{+-+} - S)\},\\]

where \[C_n^{+-+} - S = \begin{cases} \frac{C_n}{C_n}, & \text{if } S = E(C_n), \\ \frac{1}{C_n}, & \text{if } S = V(C_n). \end{cases}\]

Thus,

\[I(C_n^{+-+}) = |S| + m(C_n^{+-+} - S) = n + \min\{I(C_n), I(\overline{C_n})\}.\]

Theorem 3.45. Let \(K_n\) be a complete graph with \(n, (n \ge 3)\) vertices. Then

\[I(K_n^{+-+}) = n + I(J(K_n)).\]

Proof. The number of edges in \(K_n\) is \(\frac{n(n-1)}{2}\) which is more than n. Therefore, the number of vertices in \(K_n^{+-+}\) is \(n+\frac{n(n-1)}{2}\). If we consider \(S=V(K_n)\), then |S|=n and \(K_n^{+-+}-S=J(K_n)\). Thus, \(I(K_n^{+-+})=n+I(J(K_n))\).

Theorem 3.46. Let \(K_{1,n}\) be a star graph with n+1 vertices. Then

\[I(K_{1n}^{+-+}) = 3.\]

Proof. The number of edges in \(K_{1,n}\) is n. Therefore, the number of vertices in \(K_{1,n}^{+-+}\) is 2n+1. If we consider \(S=\{u\}\) where u is the central vertex (i.e., the vertex of degree n) of \(K_{1,n}\), then |S|=1. If the member of S is removed from \(K_{1,n}^{+-+}\), then we get \(nK_2\). Thus, \(I(K_{1,n}^{+-+})=3\). \(\square\)

Theorem 3.47. Let \(K_{a,b}(a \le b \text{ and } a, b \ge 2)\) be a complete bipartite graph with a + b vertices. Then

\[I(K_{a,b}^{+-+}) = ab + a + 1.\]

Proof. The number of edges in \(K_{a,b}\) is ab. Therefore, the number of vertices in \(K_{a,b}^{+-+}\) is a+b+ab. If we consider \(S = E(K_{a,b})\), then \(S \subset V(K_{a,b}^{+-+})\) with |S| = ab and \(K_{a,b}^{+-+} - S = K_{a,b}\). Therefore, \(m(K_{a,b}^{+-+} - S) = a+1\). Thus, \(I(K_{a,b}^{+-+}) = ab+a+1\).

Theorem 3.48. Let \(W_{1,n}(n \ge 3)\) be a wheel graph with n + 1 vertices. Then

\[I(W_{1,n}^{+-+}) = 2(n+1).\]

Proof. The number of edges in \(W_{1,n}\) is 2n. Therefore, the number of vertices in \(W_{1,n}^{+-+}\) is 3n+1. If we consider \(S=V(W_{1,n})\cup E_I\), then \(S\subset V(W_{1,n}^{+-+})\) with |S|=2n+1, where the set \(E_I\) is the collection of all edges on the cycle \(C_n\) of \(W_{1,n}\). If the members of S are removed from \(W_{1,n}^{+-+}\), then we get \(\overline{K_n}\). Thus, \(I(W_{1,n}^{+-+})=2(n+1)\).

Definition 3. Lu [28] uses θ(Cm) n to denote the book graph obtained from n-copies of C^m which share an edge in common (an n-page book with m-polygonal pages).

In the following theorem, we give the general formula for integrity of n-page book graphs with m-polygonal pages.

Theorem 3.49. If θ(Cm) n is book graph with m-polygonal pages, then

\[I(\theta(C_m)^n) = m.\]

Proof. If we choose S as the set of end vertices of the edge which is common to all the m-polygonal pages. Then θ(Cm) ⁿ − S = nP^m−². That is, the disconnected graph with n components of P^m−². Thus, I(θ(Cm) n ) = m.

4. Conclusion

In this article, one of the measures of graph vulnerability called integrity is studied. The values of vulnerability helps the researchers to construct such a communication network which remains stable after some of its nodes or communication links are get defected. The transformation graphs considered in this paper are taken to model the network system and it reveals that, how it 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 total transformation graphs of a graph. The integrity of these new graphs are presented.

Integrity of total transformation graphs are equal or greater than integrity values of graphs that have the structure. These results can help the researchers to choose a suitable topology for the network. The concept of integrity is useful in the study the robustness of the complex networks. The robustness is used to measure the ability of surviving random failures or intentional attacks. The robustness consider all the components of the network after random failures or attacks which do not bother about is there still communication is possible in all those components or not. Whereas the integrity considers only the maximum component of the network in which still the communication is possible. The integrity gives the precaution to the researchers that they should design the network in such a way that it could manage the communication in component (as large as possible) of the network after the random failures or attacks. We have the following open problems.

Open problems:

• 1. General formula for integrity of arbitrary graph.
• 2. General formula for integrity of any transformation graph.

Acknowledgement

B. Basavanagoud is supported by University Grants Commission (UGC), Government of India, New Delhi, through UGC-SAP DRS-III for 2016-2021: F.510/3/DRS-III/2016(SAP-I) dated: 29th Feb. 2016.

The authors are grateful to the anonymous referees for helpful comments on an earlier version of this paper.

References

• [1] J. Ales and R. Bacik, Strong elemination orderings of the total graph of a tree, Discrete Appl. Math. 39 (1992), 293–295.
• [2] A. Aytac¸ and S. C¸ elik, Vulnerability: Integrity of middle graphs, Selc¸uk J. Appl. Math. 9 (1) (2008), 49–60.
• [3] V. Aytac¸ and S. Bodur, Vulnerability of some splitting graphs, Bull. Int. Math. Virtual Inst. 5 (2009), 95–102.
• [4] 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.
• [5] 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.
• [6] W. Baoyindureng and M. Jixiang, Basic properties of Total Transformation Graphs, J. Math. Study 34 (2) (2001) 109–116.
• [7] C.A. Barefoot, R. Entringer, and H.C. Swart, Vulnerability in Graphs A Comparative Survey, J. Combin. Math. Combin. Comp. 1 (1987), 13–22.
• [8] C.A. Barefoot, R. Entringer, and H.C. Swart, Integrity of Trees and Powers of Cycles, Congr. Numer. 58 (1987), 103–114.
• [9] B. Basavanagoud, Quasi-total graphs with crossing numbers, J. Discrete Math. Cryptography 1 (1998), 133–142.
• [10] 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.
• [11] B. Basavanagoud, P. Jakkannavar, and I.N. Cangul, Integrity of quasi-total graphs, Proceedings of the Jangjeon Mathematical Society 4 (2020), pp. 626–639.
• [12] B. Basavanagoud, S. Policepatil, and P. Jakkannavar, Integrity of graph operations, Transactions on Combinatorics (accepted for publication).
• [13] D. Baur and R. Tindell, The connectivity of line graphs and total graphs, J. Graph Theory 6 (1982), 197–204.
• [14] M. Behzad, Graphs and their chromatic numbers, Ph. D. thesis, Michigan State University, 1965.
• [15] M. Behzad, A criterion for the planarity of a total graph, Pro. Camb. Phil. Soc. 63 (1967), 679–681.
• [16] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.

• [17] 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.
• [18] P. Dundar and A. Aytac¸, Integrity of total graphs via certain parameters, ¨ Math. Notes 76 (5) (2004) 665–672.
• [19] W.D. Goddard and H.C. Swart, On the Integrity of Combinations of Graphs, J. Combin. Math. Combin. Comp. 4 (1988), 3–18.
• [20] W. Goddard and H.C. Swart, Integrity in Graphs, Bounds and Basics, J. Combin. Math. Combin. Comp. 7 (1990), 139–151.
• [21] W. Goddard, On the Vulnerability of Graphs, Ph.D. Thesis, University of Natal, Durban, S.A., 1989.
• [22] F. Harary, Graph Theory, Addison-Wesley, Reading, 1969.
• [23] T. Hasunuma, Structural properties of subdivided-line graphs, J. Discrete Algorithms 31 (2015), 69–86.
• [24] G. Indulal and A. Vijayakumar, A note on energy of some graphs, MATCH Commun. Math. Comput. Chem. 59 (2008) 269–274.
• [25] T. Iqbalunnisa, N. Janakiraman, and N. Srinivasan, Note on iterated total graphs, J. Indian Math. Soc. New Ser. 55 (1990), 67–71.
• [26] V.R. Kulli and B. Basavanagoud, Traversability and planarity of quasi-total graphs, Bull. Cal. Math. Soc. 94 (1) (2002), 1–6.
• [27] V.R. Kulli, College Graph Theory, Vishwa International Publications, Gulbarga, India, 2012.
• [28] H.C. Lu, On large harmonious graph, Ars Combin. 91 (2009), 447–458.
• [29] 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.
• [30] Y. Shang, Subgraph robustness of complex networks under attacks, IEEE Transactions on Systems, Man and Cybernetics: Systems, DOI 10.1109/TSMC.2017.2733545.
• [31] Y. Shang, Attack robustness and stability of generalized k-cores, New J. Phys. 21 (2019), 093013.
• [32] 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.
• [33] Q. Ye, On vulnerability of power and total graphs, WSEAS Trans. Math. 11 (11) (2012), 1028–1038.