Exploring the vulnerability of any real-life network helps designers understand how strongly components or elements of the network are connected and how well they can function if there is any disruption. Any chemical structure can also be considered as a network in which the atoms correspond to the vertices, and the chemical bonds between the atoms correspond to the edges. Let \(G=(V, E)\) represent any simple graph with vertex set \(V\) and edge set \(E\). The vulnerability measure used in this paper is the paired domination integrity, defined as the minimum of the sum of any paired dominating set \(S\) of a graph \(G\) and the order of the largest component in the induced subgraph of \(V-S\). The minimum is found by considering all possible paired dominating sets of \(G\). In this paper, we obtain the paired domination integrity of the comb product of paths and cycles. In addition, we extend the study of graph vulnerability to chemical structures.
Unless otherwise stated, all graphs considered are undirected, simple, finite, and connected. All terminologies and definitions related to graphs and domination in graphs can be found in [4, 5]. A few relevant definitions and notations are presented below for a better understanding. We begin by recalling the definitions of standard graph classes namely, paths and cycles. A path \(P_n\) is a sequence of distinct vertices \(v_1,v_2,\ldots, v_n\) such that each pair of consecutive vertices \(v_i v_{i+1}\) is joined by an edge. A cycle \(C_n\) is a sequence of vertices \(v_1,v_2,\ldots, v_n, v_1\) such that \(v_i\) is adjacent to \(v_{i+1}\) for all \(i\leq n-1\), \(v_n\) is adjacent to \(v_1\), and no vertices are repeated. In other words, a cycle is a path in which the first and last vertices are the same. The order of any graph \(G\) refers to the number of vertices in \(G\). An isolated vertex is a vertex that is not adjacent to any other vertex in the graph. For a graph \(G\) with vertex set \(V\), an induced subgraph of \(G\) is defined as the graph whose vertex set is a subset \(V'\) of \(V\) and whose edge set consists of all the edges of \(G\) that have both endpoints in \(V'\). It is denoted by \(<V'>\).
Our study focuses on finding the vulnerability of any given network using a graph vulnerability parameter called paired domination integrity (PDI) [1]. The idea of combining the concepts of domination and integrity was initialized by R. Sundareswaran and V. Swaminathan (see [8]) in 2010. Later, several authors worked on this concept with different graph classes and graph operations and several variations of domination integrity were introduced. One such variation is the paired domination integrity (PDI) (see [1]) of graphs introduced in 2024. Furthermore, the idea of domination integrity was extended to real-life networks, such as PMU placement in electric power networks, transportation network systems, brain networks, etc, which can be found in [3, 6, 7]. In this paper, the authors relate the study of the paired domination integrity of the comb product of graphs to finding the vulnerability of chemical molecules since the structure of the comb product of some graphs is similar to certain chemical molecules like polymers. Exploring the vulnerability of chemical molecules to any kind of disruption helps us understand the chemical structure better. This motivated the authors to use the concept of paired domination integrity to measure the vulnerability of the comb product of paths and cycles.
The paired domination integrity of graphs is defined as follows:
Definition 1.1. The paired domination integrity of a graph \(G\) with no isolated vertices, denoted by \(PDI (G)\), is defined as \[\mathrm{PDI(G)}=\mathrm{min}\{|S|+m(G-S)\},\] where \(S\) is a paired dominating set (PDS) of \(G\) and \(m(G-S)\) is the order of the largest connected component in the induced subgraph of \(G-S\).
Definiton 2.1. [2] Let \(V(G_1)=\{v_1,v_2,\ldots,v_n\}\) and \(V(G_2)=\{u_1,u_2,\ldots,u_m\}\). The comb product of \(G_1\) and \(G_2\), denoted by \(G_1\rhd G_2\), is formed by taking one copy of \(G_1\) and \(n\) copies of \(G_2\) and placing the \(i\)-th copy of \(G_2\) onto the vertex \(v_i\) of \(G_1\) resulting in a graph of order \(nm\). The vertex \(u_r\) of \(G_2\) that is grafted onto \(v_i\) is called the identifying vertex.
Let \(G_1\rhd G_2\) be the comb product of two graphs \(G_1\) and \(G_2\). In this paper, we consider the identifying vertex to be the first vertex \(u_i\) of \(G_2\) unless otherwise mentioned.
The comb product of graphs shares structural similarity to some chemical molecules such as polymers, which motivated us to study the paired domination integrity of the comb product of graphs and thereby obtain an understanding of the stability of a molecule to any disruption. The application of graph vulnerability to chemical structures will be discussed later in this paper.
The comb product of \(P_1\) and \(P_m\), where \(m\) is any positive integer, is the path \(P_m\) itself, and thus the \(PDI(P_1\rhd P_m)=PDI(P_m)\) that has been found in [1]. On a similar note, \(P_2\rhd P_m\) is a path of order \(2m\). Therefore, \(PDI(P_2\rhd P_m)=PDI(P_{2m})\).
By further investigation, we obtain a general result for the paired domination integrity of the comb product of paths, \(PDI(P_n\rhd P_m)\), when \(n\) is odd and even. The proofs for the same are discussed in the following two theorems.
Theorem 2.2. Let \(P_n \rhd P_m\) be the comb product of two paths of order \(n\) and \(m\), respectively, where \(n\geq 4\), \(m\geq 4\) and \(n\) is odd. Then, the paired domination integrity of \(P_n \rhd P_m\) is given by \[\mathrm{PDI}(P_n \rhd P_m)= \begin{cases} \frac{n(m+2)}{2} & \ ; \ m\equiv 0\pmod{4}, \\[5pt] 2n\lceil\frac{m}{4}\rceil-n+1 & \ ; \ m\equiv 1 \pmod{4},\\[5pt] 2n\lceil\frac{m}{4}\rceil-n+3 & \ ; \ m\equiv 2\pmod{4},\\[5pt] 2n\lceil\frac{m}{4}\rceil+2 & \ ; \ m\equiv 3\pmod{4} \ \text{and}\ m\neq 6. \end{cases}\]
Proof. Let \(V(P_n\rhd P_m)\) denote the vertex set of the comb product of any two paths of order \(n\) and \(m\), respectively. Then, \(V(P_n\rhd P_m)=\{(v_1,u_1),(v_1,u_2),\ldots,(v_1,u_m),\) \((v_2,u_1),(v_2,u_2),\ldots,(v_2,u_m),(v_3,u_1),\) \((v_3,u_2),\ldots,(v_3,u_m),\ldots, (v_n,u_1),(v_n,u_2),\ldots,\) \((v_n,\\ u_m)\}\). The comb product \(P_n\rhd P_m\) contains one copy of \(P_n\) and \(n\) copies of \(P_m\) held together by \(P_n\) acting as a backbone. The \(n\) copies of \(P_m\) can be seen as the teeth of the comb. After examining the \(PDI\) of the comb product of any two paths for distinct values of \(n\) and \(m\), we generalize it for any \(P_n\rhd P_m\), where \(n\) is odd, \(n\geq 3\) and \(m\geq 4\). A general result is obtained when the following cases are considered.
Case i. \(m\equiv 0\pmod{4}\)
In this case, we select the paired dominating set \(S\) as follows to get the desired result. We choose \((\frac{m}{4})\) pairs of vertices from each of the \(n\) copies of \(P_m\), starting from the second vertex \(\{(v_i,u_2)|1\leq i\leq n\}\) and leaving two vertices between every chosen pair. That is, \(S=\{(v_i,u_j),(v_i,u_k)|1\leq i\leq n, j\equiv 2\pmod{4}\ \text{and}\ k\equiv 3\pmod{4}\}\). Thus, \(|S|=n(2(\frac{m}{4}))\). The removal of \(S\) from \(P_n\rhd P_m\) will disconnect it, and the components include a \(P_n\), isolated vertices and \(P_2\)’s, of which \(P_n\) is the largest component (see Figure 1(a)). Then, \(|S|+m((P_n\rhd P_m)-S)=\frac{nm}{2}+n=\frac{n(m+2)}{2}\). Any other paired dominating set leads to \(|S|\) being larger. Hence, we can conclude that \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=\frac{n(m+2)}{2}\).
Case ii. \(m\equiv 1\pmod{4}\)
The following procedure is considered for the selection of the \(PDI\)-set. To form the paired dominating set \(S\), we begin by choosing \(n-1\) vertices of \(P_n\) such that they are adjacent pairs of vertices of \(P_n\) (see Figure 1(b)). Further, we pick out \((\lceil\frac{m}{4}\rceil-1)\) pairs of vertices from each of the \(n\) copies of \(P_m\) such that there are two vertices between every chosen pair. Thus, the induced subgraph of \((P_n\rhd P_m)-S\) contains \(P_2\)’s and isolated vertices. The cardinality of \(S\) is \(|S|=(n-1)+n(2(\lceil\frac{m}{4}\rceil-1))=2n\lceil\frac{m}{4}\rceil-n-1\) and \(m((P_n\rhd P_m)-S)=2\). Any other paired dominating set will contain more vertices, and hence, we can conclude that \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=2n\lceil\frac{m}{4}\rceil-n-1+2=2n\lceil\frac{m}{4}\rceil-n+1\).
Case iii. \(m\equiv 2\pmod{4}\)
Here, we identify a paired dominating set \(S\) similar to the one found in Case(ii). Firstly, we choose any \(n-1\) vertices of \(P_n\) such that they are adjacent pairs of vertices of \(P_n\) forming a perfect matching. Next, we choose \((\lceil\frac{m}{4}\rceil-1)\) pairs of vertices from the \(n-1\) copies of \(P_m\) whose first vertex belongs to \(S\) and \(\lceil\frac{m}{4}\rceil\) pairs of vertices from the remaining one copy of \(P_m\). The vertices are chosen in such a way that there are two vertices between every chosen pair leading to \(m((P_n\rhd P_m)-S)\) being two. The cardinality of \(S\) is given by \(|S|=(n-1)+(n-1)(2(\lceil\frac{m}{4}\rceil-1))+2\lceil\frac{m}{4}\rceil=2n\lceil\frac{m}{4}\rceil-n+1\). The above-mentioned set is found to give the minimum value for \(|S|+m((P_n\rhd P_m)-S)\) over all possible paired dominating sets. Thus, we infer that \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=2n\lceil\frac{m}{4}\rceil-n+1+2=2n\lceil\frac{m}{4}\rceil-n+3\).
Case iv. \(m\equiv 3\pmod{4}\)
After examining the \(PDI\)-sets of \(P_n\rhd P_m\) for different values of \(n\) and \(m\), where \(n\) is odd, we identify the following paired dominating set as the \(PDI\)-set for this case. We choose \(S=\{(v_i,u_j),(v_i,u_k)|1\leq i\leq n, j\equiv 1\pmod{4}\ \text{and}\ k\equiv 2\pmod{4}\}\), that is, there are two vertices between every chosen pair in each of the \(n\) copies of \(P_m\). The induced subgraph of \((P_n\rhd P_m)-S\) also contains isolated vertices at the end of each copy of \(P_m\) as shown in Figure 2. However, \(m((P_n\rhd P_m)-S)=2\) since the largest component is a \(P_2\). The cardinality of \(S\) is \(|S|=n(2\lceil\frac{m}{4}\rceil)\) since we choose \(\lceil\frac{m}{4}\rceil\) pairs of vertices from each copy of \(P_m\). Thus, we can conclude that \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=2n\lceil\frac{m}{4}\rceil+2\). Hence, we have the desired result.
This completes the proof. ◻
We now find a general result for the \(PDI(P_n\rhd P_m)\) when \(n\) is even.
Theorem 2.3. Let \(n, m\geq 4\) and \(n\) be even. Then, the paired domination integrity of the comb product of two paths, \(P_n\rhd P_m\), is given by, \[\mathrm{PDI}(P_n \rhd P_m)= \begin{cases} \frac{n(m+2)}{2} & \ ; \ m\equiv 0\pmod{4}, \\[5pt] \frac{n(m+1)}{2} & \ ; \ m\equiv 1\pmod{4}, \\[5pt] \frac{nm}{2}+2 & \ ; \ m\equiv 2\pmod{4}, \\[5pt] \frac{nm+n+4}{2} & \ ; \ m\equiv 3 \pmod{4}. \end{cases}\]
Proof. The vertex set of \(P_n\rhd P_m\) is the same as considered in Theorem 2.2, the only difference being that \(n\) is odd. The following four cases are discussed depending on the values of \(m\).
Case i. \(m\equiv 0\pmod{4}\)
The \(PDI\) set considered here is the same as in Case(i) of the previous theorem. The result follows the same way as discussed in Theorem 2.2 (see Figure 3(a)). Hence, \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=\frac{n(m+2)}{2}\).
Case ii. \(m\equiv 1\pmod{4}\)
The \(PDI\)-set for this case is obtained in the following way. We begin by selecting any \(n-2\) vertices from the backbone \(P_n\), which is an even order path, such that the chosen vertices are all adjacent pairs of vertices of \(P_n\) as can be seen in Figure 4. Then we choose \((\frac{m-1}{4})\) pairs of vertices from each of the \(n\) copies of \(P_m\) such that there are two vertices between every chosen pair of vertices. This results in \(m((P_n\rhd P_m)-S)=2\) and \(|S|=(n-2)+n(2(\frac{m-1}{4}))=n(\frac{m+1}{2})-2\). Thus, we have \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=n(\frac{m+1}{2})-2+2=\frac{n(m+2)}{2}\). Hence, we have the desired result.
Case iii. \(m\equiv 2\pmod{4}\)
If we go through all possible paired dominating sets in this case, then we reach the paired dominating set \(S\) that gives the minimum value for \(|S|=m((P_n\rhd P_m)-S)\), the explanation of which is discussed as follows. We begin by considering all the vertices of \(P_n\) to belong to \(S\). Next, we choose \((\frac{m-2}{4})\) pairs of vertices from each of the \(n\) copies of \(P_m\) such that we leave two vertices between every chosen pair which leads to \(m((P_n\rhd P_m)-S)=2\) (see Figure 5). The cardinality of \(S\) is \(|S|=n+n(2(\frac{m-2}{4}))=\frac{nm}{2}\) and thus \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=\frac{nm}{2}+2\).
Case iv. \(m\equiv 3\pmod{4}\)
After going through all possible paired dominating sets, the \(PDI\)-set found in this case is \(S=\{(v_i,u_j),(v_i,u_k)|1\leq i\leq n, j\equiv 1\pmod{4}\ \text{and}\ k\equiv 2\pmod{4}\}\). Thus, \(|S|=n(2(\frac{m+1}{4}))\). The induced subgraph of \((P_n\rhd P_m)-S\) contains \(n\) isolated vertices, as shown in Figure 3(b), and \(P_2\)’s resulting in \(m((P_n\rhd P_m)-S)=2\). Thus, \(PDI(P_n\rhd P_m)=min\{|S|+m((P_n\rhd P_m)-S)\}=\frac{n(m+1)}{2}+2=\frac{nm+n+4}{2}\). Hence, we get the desired result.
This completes the proof for the even case of \(n\). ◻
From Theorems 2.2 and 2.3, we note that the paired domination integrity of \(P_n\rhd P_m\) is the same for any value of \(n\) when \(m\equiv 0\pmod{4}\) and hence we get the following result.
Observation 2.4. If \(P_n\rhd P_m\) denotes the comb product of two paths of order \(n\) and \(m\) respectively, then \(PDI(P_n\rhd P_m)=\frac{n(m+2)}{2}\) when \(m\equiv 0 \pmod{4}\).
Let \(n\) and \(m\) be any positive integer such that \(n,m\geq 3\). Then, we denote the comb product of cycles as \(C_n\rhd C_m\). As discussed in the previous section, we study the paired domination integrity of \(C_n\rhd C_m\) for odd \(n\) and even \(n\) separately and obtain a general result for the same. For any value of \(n\) and \(m\), the paired domination integrity of \(C_n\rhd C_m\) has been discussed in the following two theorems.
Theorem 2.5. Let \(C_n \rhd C_m\) be the comb product of two cycles of order \(n\) and \(m\), respectively, where \(n, m\geq 4\) and \(n\) is odd. Then, the paired domination integrity of \(C_n \rhd C_m\) is given by \[\mathrm{PDI}(C_n \rhd C_m)= \begin{cases} \frac{nm+4}{2} & \ ; \ m\equiv 0\pmod{4}, \\[5pt] \frac{nm+n+4}{2} & \ ; \ m\equiv 1\pmod{4}, \\[5pt] \frac{nm+6}{2} & \ ; \ m\equiv 2\pmod{4}, \\[5pt] \frac{nm-n+6}{2} & \ ; \ m\equiv 3 \pmod{4}. \end{cases}\]
Proof. If \(V(C_n\rhd C_m)\) denotes the vertex set of the comb product of two cycles of order \(n\) and \(m\) respectively, then \(V(C_n\rhd C_m)=\{(v_1,u_1),(v_1,u_2),\ldots, (v_1,u_m), (v_2,u_1),\) \((v_2,u_2),\ldots,(v_2,u_m),\ldots, (v_n,u_1),\) \((v_n,u_2),\ldots,(v_n,u_m)\}\). We discuss the following cases for any odd value of \(n\).
Case i. \(m\equiv 0\pmod{4}\)
After examining all possible paired dominating sets, we find the following \(PDI\)-set \(S\) for this case. We choose \((\frac{m}{4})\) pairs of vertices from each of the \(n\) copies of \(C_m\) such that the vertices of \(C_n\) are also included (see Figure 6(a)). Then, \(|S|=n(2(\frac{m}{4}))\). Furthermore, the induced subgraph of \(((C_n\rhd C_m)-S)\) contains only paths of order two, which leads to \(m((C_n\rhd C_m)-S)=2\). Since the paired dominating set mentioned above gives the minimum value for \(|S|+m((C_n\rhd C_m)-S)\) over all possible paired dominating sets of \(C_n\rhd C_m\), we get \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=\frac{nm+4}{2}\).
Case ii. \(m\equiv 1\pmod{4}\)
In this case, to get the desired result, we identify the following paired dominating set \(S\) as the \(PDI\)-set after examining all possible paired dominating sets. We begin by selecting \(n-1\) vertices from \(C_n\) such that they are adjacent pairs of vertices in \(C_n\). Then we choose \((\frac{m-1}{4})\) pairs of vertices from each of the \(n\) copies of \(C_m\) such that there are two vertices between every chosen pair. However, \(m((C_n\rhd C_m)-S)=3\) since the induced subgraph of \((C_n\rhd C_m)-S\) contains a path of order three formed by the vertex of \(C_n\) not in \(S\) and two of its neighbors in the corresponding copy of \(C_m\). As a result, we get \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=n-1+n(2(\frac{m}{4}))+3=\frac{nm+n+4}{2}\).
Case iii. \(m\equiv 2\pmod{4}\)
Here, we choose a paired dominating set similar to the previous case as the \(PDI\)-set with a slight difference. Firstly, we select \(n-1\) vertices of \(C_n\) that are adjacent pairs of vertices in \(C_n\). Then we choose \((\frac{m-2}{4})\) pairs of vertices from the \(n-1\) copies of \(C_m\) corresponding to the \(n-1\) vertices mentioned earlier (see Figure 6(b)). Furthermore, we select \((\frac{m+2}{4})\) pairs of vertices from the remaining copy of \(C_m\). The pairs of vertices are chosen such that the induced subgraph of \((C_n\rhd C_m)-S\) contains either \(P_2\)’s or isolated vertices. Consequently, we get \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=n-1+(n-1)2(\frac{m-2}{4})+2(\frac{m+2}{4})+2=\frac{nm+6}{2}\).
Case iv. \(m\equiv 3\pmod{4}\)
In this case, we consider a paired dominating set \(S\) similar to the previous case as the \(PDI\)-set, but the number of pairs of vertices chosen is slightly different. Firstly, let \(n-1\) vertices of \(C_n\), which are adjacent pairs of vertices, belong to \(S\). Then we pick out \((\frac{m-3}{4})\) pairs of vertices from the \(n-1\) copies of \(C_m\) corresponding to the \(n-1\) vertices mentioned earlier. In addition, we choose \((\frac{m+1}{4})\) pairs of vertices from the remaining copy of \(C_n\), including the vertex of \(C_n\) common to this copy. While choosing the pairs, we make sure to leave two vertices between every chosen pair to get a lesser cardinality of \(S\), which leads to \(m((C_n\rhd C_m)-S)=2\). The induced subgraph of \((C_n\rhd C_m)-S\) may contain isolated vertices depending on the value of \(m\). As a result, we can conclude that \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=n-1+(n-1)2(\frac{m-3}{4})+2(\frac{m+1}{4})+2=\frac{nm-n+6}{2}\).
This completes the proof. ◻
Theorem 2.6. For even \(n\) and \(n, m\geq 4\), the paired domination integrity of the comb product of two cycles, \(C_n\rhd C_m\), is given by,
\[\mathrm{PDI}(C_n \rhd C_m)= \begin{cases} \frac{nm+4}{2} & \ ; \ m\equiv 0,2\pmod{4}, \\[5pt] \frac{nm+n+4}{2} & \ ; \ m\equiv 1 \pmod{4} \ \text{and}\ m\neq 5,\\[5pt] \frac{nm-n+4}{2} & \ ; \ m\equiv 3 \pmod{4},\\[5pt] \end{cases}\]
Proof. Here, we obtain a general result for paired domination integrity of \(C_n\rhd C_m\) when \(n\) is even. As mentioned in the previous theorem, \(V(C_n\rhd C_m)=\{(v_1,u_1),(v_1,u_2),\ldots, \\(v_1,u_m), (v_2,u_1),(v_2,u_2),\ldots,\) \((v_2,u_m),\ldots, (v_n,u_1),(v_n,u_2),\ldots,\) \((v_n,u_m)\}\). We discuss the following three cases for distinct values of \(m\).
Case i. \(m\equiv 0,2\pmod{4}\)
Let \(m\equiv 0\pmod{4}\). We identify the following \(PDI\)-set \(S\) after taking minimum over all possible paired dominating sets of \(C_n\rhd C_m\). We begin by taking all the vertices of \(C_n\) in \(S\). Then we choose \(2(\frac{m}{4})-1\) vertices from each of the \(n\) copies of \(C_m\) such that the induced subgraph of \((C_n\rhd C_m)-S\) contains only \(P_2\)’s as shown in Figure 7(a). Thus, \(m((C_n\rhd C_m)-S)=2\). We note that the vertices of \(C_n\) are not adjacent pairs in \(S\) that induces a perfect matching. However, each of them is paired with a vertex chosen from the corresponding copy of \(C_m\). These selected vertices form the \(PDI\)-set that induces a perfect matching. Hence, we can conclude that \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=n+n(\frac{2m}{4}-1)+2=\frac{nm+4}{2}\).
Now, let \(m\equiv 2\pmod{4}\). Here, we get the same value of \(PDI\) as found above, but the \(PDI\)-set \(S\) is different. Firstly, all vertices of \(C_n\) belong to \(S\) and are adjacent pairs of vertices. In addition, we choose \((\frac{m-2}{4})\) pairs of vertices from each of the \(n\) copies of \(C_m\). This completes the paired dominating set for this case. Therefore, we get \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=n+n(2(\frac{m-2}{4}))+2=\frac{nm+4}{2}\).
Case ii. \(m\equiv 1\pmod{4}\)
Here, to get the desired result, we choose a paired dominating set \(S\) similar to the one considered for \(m\equiv 2\pmod{4}\) as the \(PDI\)-set. That is, \(\{(v_i,u_1)|1\leq i\leq n\}\in S\) and then we choose \((\frac{m-1}{4})\) pairs of vertices from each of the \(n\) copies of \(C_m\) such that the induced subgraph of \((C_n\rhd C_m)-S\) contains \(P_2\)’s and isolated vertices. Consequently, we get \(PDI(C_n\rhd C_m)=min\{|S|+m((C_n-C_m)-S)\}=n+n(2(\frac{m-1}{4}))+2=\frac{nm+n+4}{2}\). However, we note that for \(m=5\), \(m((C_n\rhd C_m)-S)=1\) (see Figure 7(b)) and hence \(PDI(C_n\rhd C_5)=n+n(2(\frac{m-1}{4}))+1=\frac{nm+n+2}{2}\).
Case iii. \(m\equiv 3\pmod{4}\)
This case also follows a similar way of selection of vertices as the previous cases, but the number of pairs of vertices chosen from the copies of \(C_m\) is different. We begin by considering \(\{(v_i,u_1)|1\leq i\leq n\}\in S\) and then we choose \((\frac{m-3}{4})\) pairs of vertices from each of the \(n\) copies of \(C_m\) such that there are two vertices between every chosen pair. Then, \(|S|=n+n(2(\frac{m-3}{4}))=\frac{nm-n}{2}\) and \(m((C_n\rhd C_m)-S)=2\). Therefore, by taking the minimum over all possible paired dominating sets, we can conclude that \(PDI(C_n\rhd C_5)=\frac{nm-n}{2}+2=\frac{nm-n+4}{2}\).
This completes the proof. ◻
In the following section, we discuss how paired domination integrity can be used to measure the vulnerability of a chemical molecule that is modeled by the comb product of paths and cycles.
In chemistry, some chemical structures such as polymers, dendrimers, and graphene can be represented by the comb product of graphs. In our study, we measure the vulnerability of the comb product of paths and cycles, which acts as a graph model to represent the chemical structures mentioned above and to analyze their stability. Here, the vertices represent the atoms and the edges indicate the chemical bond between the atoms. The concept of paired domination integrity helps us to analyze the stability of a chemical structure against any disruption. The disruption may be caused by high temperature, exposure to radiation, mechanical stress, hydrolysis, addition of impurities, etc. In addition, it helps identify the significant nodes required for maintaining the structural integrity of a molecule. For example, let us consider a polymer. Polymers are large chemical molecules made up of repeating units called monomers. If the structure of the polymer is disrupted because of some factors mentioned earlier, the remaining part of the molecule may function on the basis of the extent of the disruption. An understanding of the critical nodes in a molecule is essential for the synthesizing of more stable polymers for several applications.
For better understanding, let us consider a graphene molecule (C) that has a structure similar to that of the comb product of cycles. Graphene is an allotrope of carbon in two dimensions. Its constituent carbon atoms are arranged in a hexagonal pattern. A single graphene sheet is made up of a single layer of carbon atoms organized in a honeycomb pattern. The vertices represent the carbon atoms, and the covalent bonds between the carbon atoms are represented by edges, as shown in Figure 8.
In a graphene molecule, each carbon atom is bonded to three neighbouring carbon atoms through covalent bonds and each hexagonal ring has alternating double bonds between carbon atoms. These covalent bonds are represented by edges of a graph. The graphene molecule considered in Figure 8 has three rows of hexagonal rings joined together as shown above. After going over all possible paired dominating sets of the molecule, we identify the following \(PDI\)-set. We choose the pairs of carbon atoms that has double bonds between them from the first and the last rows of hexagonal rings of the molecule. Furthermore, the induced subgraph of \(C-S\) contains pairs of carbon atoms joined by a covalent bond and isolated carbon atoms. As a result, \(PDI(C)=min\{|S|+m((C-S)\}=20+2=22\). We have found the paired domination integrity for a particular size of graphene layer. The value might vary depending on the size.
The concept of graph vulnerability in chemical graphs can have several significances. A higher domination integrity value may imply that the molecule can withstand more structural changes without losing stability. Domination integrity can help predict how the stability of a molecule varies due to minor disturbances such as temperature or pressure changes. The notion of domination integrity can be used to make more stable molecules that can resist disruptions. Understanding the vulnerability of a molecule through graph vulnerability parameters gives an idea of the overall structural integrity of the molecule.
In this paper, the authors have discussed the vulnerability of comb product of paths \((P_n\rhd P_m)\) and cycles \((C_n\rhd C_m)\) using the concept of paired domination integrity. A general result is obtained for the same for odd and even values of \(n\). This notion of graph vulnerability can be investigated for several graph classes and graph operations. In addition, we extend the study to explore the vulnerability of chemical molecules by taking an example of a graphene molecule. Further research can be conducted to study the domination integrity of various chemical molecules, providing valuable insights into their structural vulnerabilities. The idea of vulnerability of graphs is an area that can be expanded to several other real-life networks.