On very strongly perfect Cartesian product graphs

1.   Introduction

Throughout this paper we consider simple, finite and connected graphs. We adopt the notation $G = (V, E),$ where $V = V(G)$ represent vertex set of $G$ and $E = E(G)$ is an edge set of $G$. If $\left|V(G)\right| = \phi$ then $G$ is known as empty graph. The number of edges incident on a vertex $b$ gives the degree of a vertex $b$ that is indicated through $deg(b)$. Graph $G$ is said to be $r$-regular, if $deg(v) = r$ for every $v\in V(G)$. A path from vertex $u$ to a vertex $v$ is an alternating sequence of vertices and edges which connects $u$ and $v,$ such that all vertices and edges in a sequence are distinct. The number of edges in a path represent its length; which is denoted by $P_k$ (a path of length $k$). A cycle is a path in which both the end vertices are equal. The number of edges in a cycle represent its length; which is denoted by $C_n$ (cycle of length $n$). The length of the shortest cycle in $G$ is called the girth of $G,$ denoted by $gr(G)$. A chord of a graph $G$ is an edge which connects two nonadjacent vertices in the cycle. For a graph $G,$ a subset $I \subseteq V(G)$ is said to be independent, if the subgraph induced by vertex set of $I$ has no edge. The number of vertices in a maximum independent set is called as independence number which is denoted by $\alpha (G)$. An independent set is said to be strong, if each vertex of $G$ is in an independent set of $G$ which meets all maximal complete subgraphs of $G$. A clique of a graph is its maximal complete subgraph ("maximal" with respect to set-inclusion), and the minimum number of cliques required to cover all the vertices of graph $G$ is called the partition number, denoted by $\theta(G)$. The maximum size of clique gives clique number; denoted by $\omega (G)$. Graph $G$ with minimum number of colors, such that no two adjacent vertices receives the same color called chromatic number which is denoted by $\chi (G)$. A graph $G$ is said to be perfect ^[4] if for every induced subgraph $S$ of $G$, $\chi (S) = \omega (S)$ and it is called strongly perfect graph (SPG) ^[3] if, for every $S$ there is an independent set meeting all maximal complete subgraphs of $S$. Graph $G$ is said to be co strongly perfect if both $G$ and $\overline{G}$ are $SPG$. If for every induced subgraph $S$ of $G,$ each vertex of $S$ belongs to a strong independent set of $S,$ then we say that $G$ is very strongly perfect graph $(VSPG)$. $\varGamma_G(x) = \{y / xy \in E\}$, denotes set of all neighbors of '$x$' in $G$.

Let $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be any two graphs. The Cartesian product of $G_1$ and $G_2$, denoted by $G = G_1 \square G_2$ whose vertex set is $V = V_1 \times V_2$ and $A_i A_j \in E$ for $A_i = (a_i, b_i), \; A_j = (a_j, b_j)$ if and only if either

(ⅰ) $a_i a_j \in E_1$ and $b_i = b_j,$ or

(ⅱ) $a_i = a_j$ and $b_i b_j \in E_2$.

Ravindra et al. ^[8] studied the Cartesian products of a perfect graph and characterized various sufficient conditions for perfect Cartesian products. They also proved perfect graph conjecture for Cartesian product graphs. Meyniel ^[11] proved that a graph $G$ is perfect if it has no induced subgraph $C_{2k+1}$ or $C_{2k+1}+ e,$ $k \geq 2$. Nowadays such kind of graph is known as a Meyniel graph. Further Hoàng ^[2] proved the Meyniel conjecture, a graph $G$ is $VSPG$ if and only if it is Meyniel. Gandal et al. ^[10] studied the products of $VSPG$ and they characterized various conditions on graphs to be $VSPG$. Berge et al. ^[3] proved that every $SPG$ is perfect, not conversely, as $\overline{C}_{2k},$ $k > 2,$ is perfect but not $SPG$. Some interesting classes of perfect graphs are summarized by S. Hougardy ^[16]. $SPG$ conjecture for $(K_{4}-e)$-free graph was studied by Tucker ^[1] and Parthasarathy et al. ^[12]. Kwasnik et al. ^[13] proved the necessary and sufficient condition for the generalized Cartesian product graphs to be $SPG$. Chudnovsky et al. ^[14] provides a polynomial time algorithm to determine the maximum graph weight clique in perfect graphs with no induced $\overline{C}_{k}, \; k \geq 5,$ and no induced cycle $C_{6}$. The independence number of triangle-free regular graphs are investigated by Ayat et al. ^[17]. Further, they proved the result for 3-regular triangle-free graph whose independence ratio is more than 3/8.

Graph theory results are applied to problems in communications which are increasingly used in wireless multi-hop networks of military and civilian applications like Wireless Sensor Networks $(WSNs)$, underwater sensor networks, vehicular networks, and mesh networks. Carlos-Mancilla et al. ^[15] studied relevant work on $WSN$. It presents the evolution, design, and implementation of some important $WSN$ techniques and the most used protocols and standards to improve the sensor applications. In this paper, for $WSN,$ we introduce the strong independent set of master nodes which receives the data from all the slave nodes and send it to the user.

As maintained above Ravindra et al. ^[8] proved that $G_1 \square G_2$ is perfect if and only if it has no induced subgraph $C_{2k + 1}, \; k \geq 2$. This result motivated us to verify the meyniel conjecture for the Cartesian product of two graphs. In this paper we proved that $G_1 \square G_2$ is $VSPG$, if and only if it is bipartite. Berge et al. ^[3] investigated some classifications of strongly perfect graphs and proved that $G$ is $SPG,$ if it has no $P_4$ as an induced subgraph. They also gave some examples of the graph that are not $SPG$. The classes of perfectly orderable graphs were studied by Chavtal ^[18]. With these results, we characterize the Cartesian product of graphs which can be realized as $VSPG$.

For more information on graph theory, the reader may refer ^[5,7].

2.   Very strongly perfect graph ($VSPG$)

Definition 1. For every induced subgraph $S$ of $G,$ if each vertex of $S$ belongs to a strong independent set of $S,$ then a graph $G$ is called $VSPG$.

Example 1. The graph is shown in Figure 1 is a $VSPG$ with strong independent sets, corresponding to each vertex of the graph (see Table 1).

From the definition of $VSPG$ we get the simple corollary:

Corollary 2.1. If $G_1 \square G_2$ is $VSPG$ then all its induced subgraphs are $VSPG$.

Proof. It is clear from the definition of $VSPG$.

We essentially need following two Lemmas throughout this article.

Lemma 2.2. ^[2] $G$ is $VSPG$ if and only if it has no induced $C_{2k + 1}$ or $C_{2k + 1} < /italic > < italic > + e, \; k \geq 2$.

Lemma 2.3. ^[6] $G_1$ and $G_2$ are bipartite if and only if $G_1 \square G_2$ is bipartite.

G. Ravindra ^[9] defines the concept of starter in graph $G$ as follows. The starter in graph G means a cycle $C: wu_0 u_1 u_2 \cdots u_k w$ such that

(ⅰ) $u_0$ is non-adjacent to the vertices $u_2, u_3, \cdots, u_k$.

(ⅱ) There is no edge between $w$ and $u_1$ (Triangle free).

(ⅲ) There exists an independent set $I,$ with $u_1$ and $u_k$ which hits every maximal complete subgraph of graph $G-u_0$.

Lemma 2.4. ^[9] $G$ has a starter then there is $C_{2k + 1}$ or $C_{2k + 1} + e, \; k \geq 2$.

For simplicity, in a graph $G = G_1 \square G_2$ we use the following notation. If

and

where $m, \; n \geq 2$, then $A^p_q = (a_p, \; b_q)$ represent the vertex on $p^{th}$ floor and $q^{th}$ position in a graph $G$. Therefore $V (G) = \{A^p_q / \ 1 \leq p \leq n$ and $1 \leq q \leq m\}$ which gives $|V (G)| = mn$. Vertices $A^i_j$ and $A^r_s$ are said to be adjacent if either $(a_i, \; a_r) \in E_1$ and $b_j = b_s$ or $(b_j, \; b_s) \in E_2$ and $a_i = a_r$.

Theorem 1. $G_1 \square G_2$ is $VSPG$ if and only if $G_1 \square G_2$ is bipartite.

Proof. Suppose $G = G_1 \square G_2$ is $VSPG$. By definition of $G,$ $G_1$ and $G_2$ are its induced subgraphs. Further, by Corollary 2.1 graphs $G_1$ and $G_2$ are $VSPG$ and by Lemma 2.2 they do not have induced $C_{2k+1}, \; k\geq2$. To prove that graphs $G_1$ and $G_2$ are bipartite it is sufficient to show that both $G_1$ and $G_2$ are $K_3$ free. For, if not, then $K_3 \square K_3$ contains an induced $C_5+ {e},$ illustrated in Figure 2 contradicting the assumption. So, we proved that graphs $G_1$ and $G_2$ are bipartite. Thus, by Lemma 2.3, $G = G_1 \square G_2$ is bipartite.

Conversly, suppose $G = G_1 \square G_2$ is bipartite. Thus $G$ has no $K_p, \; p\geq 3$ as an induced subgraph; that implies, $G$ has only $K_2$ as an maximal complete subgraph.

Now to prove that graph $G$ is a $VSPG$. We prove the result by induction on the number of vertices of graph $G$. Suppose the result holds for every graph of the order less than '$mn$'. If there exists a vertex $A^i_j$ in a graph $G$ which hits all maximal complete subgraphs of graph $G,$ then $I = \{A^i_j\}$ is a strong independent set of $G$. If not, then choose a vertex $A^p_q$ not adjacent to $A^i_j$ with the condition that they have the maximum number of vertices common in their neighborhoods. By the induction hypothesis, $H = G-{A^i_j}$ is $VSPG;$ thus there is a strong independent set $F$ of $H$ which includes $A^p_q$. Let $M$ be a connected component of $G$ such that $V(M) = V(G)- V(\Gamma_G (A^i_j))-(A^i_j)$.

Consider a set $I = \{A^i_j\} \cup (F \cap M)$. Clearly, there is no edge which has one end in $A^i_j$ and the other in $M$. That implies $I$ is an independent set. Now it is enough to prove that $I$ is a strong independent set of $G$. We will prove this result by contradiction. Assume some maximal complete subgraph $K_{2}$ in $G$ which is disjoint from $I$ i.e. $K_{2} \cap I = \phi$. From assumption, clearly $K_{2} \cap M \neq \phi \; \cdots (1)$. If not, then $K_{2} \subseteq G - M,$ as $G - M$ is $VSPG$ with independent set $\{A^i_j\}$ gives $K_{2} \cap \{A^i_j\} \neq \phi,$ contradicts $K_{2} \cap I = \phi$. Also (1) gives $K_{2} \subseteq M \cup \Gamma_G (A^i_j)$ Finally, $K_{2} \cap \Gamma_G (A^i_j) \neq \phi,$ Otherwise $K_{2} \subseteq M$ and $G-\{A^i_j\}$. As $G-\{A^i_j\}$ is $VSPG$ with strong independent set $F,$ which yeilds $K_{2} \cap (F \cap M) \neq \phi$; contradicts $K_{2} \cap I = \phi$. Also from (1), $K_{2} \cap M \neq \phi$. Thus we conclude that, $K_{2} = (A^i_a, \; A^b_a)$ has one end in $\Gamma_G (A^i_j)$ and other is in $M$. Consider $A^i_a\in \Gamma_G (A^i_j)$ and $A^b_a \in M$ but not in $F,$ otherwise $A^b_a \in (F \cap M)$ and so $K_{2} \cap \ (F \cap M) \neq\phi,$ that implies $K_{2}\cap I \neq \phi;$ contradicts the assumption $K_{2} \cap I = \phi$. Clearly $\Gamma_G (A^i_j)$ and $M$ are distinct set of vertices. Thus $A^b_a \notin \Gamma_G (A^i_j)$ at all. As $H = G-\Gamma_G (A^i_j)$ is connected and $VSPG$ with strong independent set $F$. That implies $K_{2} \cap F \neq \phi;$ since $A^b_a \notin F,$ that implies $A^i_a \in F$.

Set, $A = \Gamma_G (A^i_a) \cap M,$ by (1) we have $A \neq \phi$. Otherwise, $K_{2}$ is contained in $\Gamma_G (A^i_a)$ only, Gives $K_2 \cap M = \phi;$ contradicts Eq (1). Also $A^p_q$ does not lie in $A,$ since $F$ contains both $A^p_q$ and $A^i_a$. As $H$ is a connected subgraph, there exists a shortest path $p$ from a vertex $A^p_q$ to a vertex in $A$. We may assume the vertices of path $p$ as $A^b_a\, A^b_d\, \cdots A^p_q$ with only $A^b_a \in A$ and $A^b_d, \cdots, A^p_q$ do not lie in $A$.

Further by the condition, $A^i_j$ and $A^p_q$ have a maximum number of vertices common in their neighborhood. Therefore we get a vertex $A^i_q$ that lies in $\Gamma_G (A^p_q)$ and $\Gamma_G (A^i_j)$ but not in $\Gamma_G (A^b_a)$. Also there must be an edge between $A^i_q$ and $A^i_a$ [that is $e = A^i_qA^i_a]$. If not, then the cycle $A^i_j\, A^i_a\, A^b_a\, A^b_d \cdots\; A^p_q \, A^i_q \; [{\rm with}\; A^i_a = u_0]$ would satisfy all conditions of Lemma 2.4, which yields $C_{2k + 1}, \; k \geq 2,$ illustrated in Figure 3. This contradicts the assumption.

Let there exist an edge between the vertices $A^i_q$ and $A^i_a,$ that is, $e = A^i_qA^i_a$. As $A^i_q$ lies in $\Gamma_G (A^i_j),$ there exist an edge between vertices $A^i_q$ and $A^i_j,$ that is, $e = A^i_qA^i_j$. Also we have $A^i_a$ in the $\Gamma_G (A^i_j)$ that gives an edge between the vertices $A^i_a$ and $A^i_j$. This results into the odd induced cycle of length three, i.e, $C_3$ illustrated in Figure 3. Again contradicts the assumption that $G$ is bipartite. Thus we conclude that $I$ is a strong independent set of $G$. That implies $G$ is $VSPG$.

Remark. Theorem 1, asserts the validity of the $VSPG$ conjecture for Cartesian product graphs.

Open access: This article is distributed under the terms of Github. Github Inc is a provider of Internet hosting for software development. Free GitHub accounts are commonly used to host open-source projects.

The code that uses the above algorithm can be found by the link given below. (Available from: https://github.com/GaneshGandal/Maths_Phd).

Chvatal ^[18] characterized the classes of strongly perfect graphs which include all comparability graphs. A graph $G$ is said to be a comparability graph, if its vertices are linearly ordered in such a way that no subgraph is induced with the vertices $a, b, c$ and edges $ab, bc$ such that $a < b < c$. They are also perfectly orderable, given the correct order by the topographic sequence of the graph's transition orientation. In ^[18], the subsequent proposition was proved on the perfectly orderable graph $G$ with $C$ being the set of all complete subgraphs (not dominating clique) of $G$.

Lemma 2.5. ^[18] $C$ is a set of pairwise adjacent vertices in graph $G$ such that each $w \in C$ has a neighbour $p(w) \notin C$. So the vertices of $p(w)$ are pairwise nonadjacent. If there is perfect order $<$ with $p(w) < w$ for all $w \in C$ then some $p(w)$ are adjacent to all the vertices in $C$.

Lemma 2.6. ^[3] If $G$ is strongly perfect, then $G$ does not have $C_{2k+1},$ for each $k\geq 2$ and $\bar{C_{2n}},$ for $n\geq 3$ as induced subgraphs.

Lemma 2.7. ^[6] $G_1 \square G_2$ strongly perfect if and only if both $G_1$ and $G_2$ are bipartite.

Now, we characterize the Cartesian product of graphs which can be realized as $VSPG$.

Theorem 2. The following properties are equivalent.

(i) $G_1 \square G_2$ is $SPG$.

(ii) $G_1 \square G_2$ is $VSPG$.

(iii) $G_1 \square G_2$ is bipartite.

(iv) $G_1 \square G_2$ is perfectly orderable.

Proof. Let $G_1 \square G_2$ be strongly perfect. By Lemma 2.7, both $G_1$ and $G_2$ do not have induced $C_{2k + 1}, \; k \geq\; 1$. Therefore, by Theorem 1, $G_1 \square G_2$ is $VSPG$. Let $G_1 \square G_2$ be $VSPG$. Since $G _1$ and $G_2$ are induced subgraphs of $G_1 \square G_2,$ by Corollary 2.1, both $G_1$ and $G_2$ are $VSPG$. As every $VSPG$ is $SPG$, by Lemma 2.6, $G_1$ and $G_2$ do not contain $C_{2k+1}, \; k \geq 2$ as an induced subgraph. For $G_1$ and $G_2$ to be bipartite, it is sufficient to prove that both $G_1$ and $G_2$ are free from induced $C_3$. Suppose $G_2$ has induced $C_3$ which includes the vertices, say $v_a, \; v_b$ and $v_d$. Since $G_1$ is connected, there is an edge, say $(u_i, \; u_j) \in E (G_1)$. For simplicity, set $E_k = (u_k, \; v_a),$ $F_k = (u_k, \; v_b),$ $M_k = (u_k, \; v_d),$ for $k = i, \; j$. Let $H$ be the subgraph of a graph $G_1 \square G_2$ induced by the vertices $E_k, \; F_k, \; M_k$. Since $G_1 \square G_2$ is $VSPG,$ $H$ is also $VSPG$. Let $I_h$ be a strong independent set of $H$. Note that the sets $\{E_i, \; F_i, \; M_i\}, \{E_j, \; F_j, \; M_j\}$ and the sets with two vertices that forms an edges are all maximal complete subgraphs of $H$ (shown in Figure 4). Without loss of generality, we may assume that $E_i \in I_h$ which implies that $F_i$, $M_i \notin I_h$. Since $\{F_i, \; F_j\}$ is a maximal clique there must be $F_j \in I_h$ which implies that $E_j, M_j \notin I_h$. But then, $I_h \cap \{M_i, \; M_j\} = \phi,$ which contradicts the assumption of $I_h$. Thus we conclude that $G_1$ and $G_2$ have no induced subgraph $C_3$.

Therefore $G_1$ and $G_2$ are bipartite graphs with a bipartition, say $V(G_1) = V_{11} \cup V_{12}$ and $V (G_2) = U_{21} \cup U_{22}$ of $G_1$ and $G_2$ respectively. That implies, $(V_{11} \times U_{21} \cup V_{12} \times U_{22}) \cup (V_{11} \times U_{22} \cup V_{12} \times U_{21})$ yields bipartition of $V (G_1 \square G_2)$.

Let $G_1 \square G_2$ be a bipartite graph with bipartition $V = V_1 \cup V_2,$ such that every edge has one end in $V_1$ and other in $V_2$. It implies every induced subgraph of $G_1 \square G_2$ is free from the linearly ordered relation $' < '$ with vertices $a, \; b, \; c$ and edges $ab, \; bc$ such that $a < b < c$. That implies $G_1 \square G_2$ is a comparability graph which is the class of perfectly orderable graph.

We wish to prove that $G_1 \square G_2$ with perfect order $' < '$ is strongly perfect. That means to prove that there is an independent set $I$ which meets all the maximal complete subgraphs in a graph $G_1 \square G_2$. As $G_1 \square G_2$ is a perfectly orderable, there is a perfect ordering of sequences of vertices from $v_1$ to $v_n,$ say $v_1 v_2 \cdots v_n$. Set $I = \{v_j /\; p(v_j) = v_i \in I \; {\rm for\; all}\; i < j\}$. Let $Q$ be any maximal complete subgraph in $G_1 \square G_2.$ we need to prove that $Q \cap I \neq \phi$. We prove result by contradiction, suppose $Q \cap I = \phi$. As $Q$ is a maximal, for each $u \in Q$ its neighbour $p(u) \in I$ with $p(u) < u$. By Lemma 2.5, there exist a vertex $v_k \in I$ which is adjacent to all vertices in $Q$. Thus $Q$ can be extended to $Q \cup \{v_k\}$ as a maximal complete subgraph, which contradicts that $Q$ is maximal. Hence $G$ is strongly perfect.

Berge and Dutch ^[3] present a characterization of strongly perfect graphs. Complement of $SPG$ need not be a $SPG,$ For example, an even cycle of length more than four is $SPG$ however; its complement need not be a $SPG$. By definition of $SPG,$ it is simple to see that every induced subgraph of a graph $G$ is $SPG.$ A graph $G$ is said to be co strongly perfect if both $G$ and $\overline{G}$ are $SPG$.

Theorem 3. $G_1 \square G_2$ is co strongly perfect if and only if $G_1$ or $G_2$ is $K_2$ and the other is a tree.

Proof. Suppose $G_1 \square G_2$ is co strongly perfect. Therefore by Lemma 2.6, $G_1 \square G_2$ does not contain $C_{2n}, \; n \geq 3$. Also by Lemma 2.7, if $G_1 \square G_2$ is strongly perfect, then both $G_1$ and $G_2$ are bipartite. Further, by Lemma 2.3, if $G_1$ and $G_2$ are bipartite then $G_1 \square G_2$ is also bipartite. Finally, we get $G_1 \square G_2$ is $C_{2n}, \; n \geq 3,$ free bipartite graph. Now to prove that $G_1$ or $G_2$ is $K_2$ and the other is a tree. We prove the result by contradiction, suppose $G_2$ is not a tree. Let $G_2$ be a connected cyclic graph. Since $G_2$ is bipartite it has no odd cycle. Without loss of generality, we may consider, $G_1 = K_2$ and $G_2 = C_4$ then $K_2 \square C_4$ gives induced $C_6: A_1 A_2 A_3 B_3 B_4 B_1$, illustrated in Figure 5. Contradicts the assumption that $G_1 \square G_2$ is a $C_{2n}, \; n \geq 3,$ free bipartite graph.

Conversely, Suppose $G_1$ is $K_2$ and $G_2$ is a tree of $n$ vertices. Therefore $G_2$ is a connected acyclic graph with $(n-1)$ edges. We prove result by contradiction, suppose $G_1 \square G_2$ is not co strongly perfect. That implies $G_1 \square G_2$ contains $C_{2n}$ for, $n \geq 3$. Since we have $G_1$ is $K_2 = (u_1, u_2),$ define $T = \{v_j\in V(G_2): (u_i, v_j)\in V(G_1 \square G_2),$ for some $u_i\in V(G_1)\}$ where $i = 1, \; 2.$ As $G_1 = K_2,$ clearly if $G_1 \square G_2$ have $C_{2n}, \; n \geq 3,$ then it is easy to see that $V(C_{2n})\subseteq T \times \{u_i\},$ for some $u_i\in V(G_1),$ which is an induced subgraph of $G_2$. Contradicts the assumption that $G_2$ is acyclic.

3.   Wireless sensor network-($WSN$)

The development of $WSN$ application is essential, as it is a sustainable and accurate solution in monitoring different environmental parameters that would affect crop development. The various parameters that affect crop development are temperature, humidity of the surroundings, soil moisture, PH value and electrical conductivity. The farming decisions are majorly dependent on close monitoring of these parameters. To achieve low cost and sustainable reproduction of crops, the development of a sensor-based communication model is required. The strong independent set algorithm presented in this work is useful to find the optimal set of master nodes to communicate with the slave nodes and user.

The bidirection communication between the nodes is handled by the Xbee module. Xbee operates over a range of 100–200 meters. The slave nodes never transmit data without receiving a request from the master node. A master node is a node that receives the data from slave nodes and then sends it to the user. Now we aim to find the optimal set of master nodes that receives the data from all slave nodes and control the given system of network. The mathematical model of range-based cooperative localization is described as follows. As is shown in Figure 6, consider a sensor network consisting of $N$ sensor nodes that represents vertex set of graph $G$ i.e $\mid V(G)\mid = N$. The different nodes in the range are joined by an edge i.e, if the nodes $f_i$ and $f_j$ are in the range, then join them by an edge $E_{i, j}$ where $E_{i, j}$ represents the edge between the $i^{th}$ and $j^{th}$ node in the network. Since the given graph is undirected, order of $E_{i, j}$ and $E_{j, i}$ is not important i.e. $E_{i, j}$ = $E_{j, i}$. Let $S_{i}^{T}$ and $S_{i}^{F}$ represent the temperature and fertility sensors respectively corresponding to the $i^{th}$ node $f_i$.

Various methods are used in $WSN$ to select the set of master nodes e.g. cluster method, the grid method, etc. The random network considered in this application is shown in Figure 6 and their ranges are represented in Table 2. The optimized set of master nodes is selected from clusters using the proposed strong independent set algorithm. The clusters are formed considering the slave nodes that can communicate with master nodes.

Now we formulate the data represented in Table 2, into a graph. The vertex set and edges set must be determined within the problem. In the graphical model presented for $WSN,$ the vertex set represents a specific sensor node and the edge set represents the corresponding range. Table 3, is a representation of different sensor nodes which are in the same range.

In Table 3, the (*) sign illustrates the sensor node with the corresponding range. Now establish the data graphically as follows. A graph $G$ can be effectively implemented in finding master nodes that receive (collect) the data from slave nodes. Further, these master nodes send the collective information to the user through $WSN$ to control the given system. That is using a minimum number of master nodes we control the entire system smoothly. Let $V (G)$ represents the sensor node in $WSN$. The different nodes recorded at the same range are joined by an edge for graphical representation.

Method to find master nodes:

An algorithm is developed for Theorem 2.6, which is discussed in this work and is applied for the case study as shown in Figure 6. Select any arbitrary vertex, say $v = f_4$ from the graph $G$. If the vertex $f_4$ hits all maximal complete subgraphs of $G$ then $I = {f_4}$. Otherwise, select a vertex $f_7$ from $S$ = $G - f_4$ which is nonadjacent to $f_4$ with the condition that $f_4$ and $f_7$ shares maximum numbers of vertices in their neighborhoods. As $S$ = $G - f_4$ is $VSPG,$ that implies there is a strong independent set $F$ which includes $f_7$ and hits all maximal complete subgraphs of $S$. Let $M$ be a connected component of $G$ such that $V (M) = V (G) - V (\Gamma_G (f_4)) - {f_4}$. Thus, from Figure 6, we get $F = \{f_7, \; f_{14}\}$ and $M = \{f_6, \; f_7, \; f_8, \; f_9, \; f_{10, } \; f_{11, }\; f_{12, }\; f_{13, }\; f_{14}\}$; that implies

Thus there exists a strong independent set $I = \{f_4, f_7, f_{14}\}$ which meets all the maximal complete subgraphs of a graph $G$. From the above analysis, it is observed that nodes $f_4,$ $f_7,$ and $f_{14}$ are the most affecting conditions in the case of $WSN$. We call them master nodes, as they receive the data from all slave nodes. The master node $f_4,$ receives the data from slave nodes $f_1,$ $f_2,$ $f_3,$ and $f_5$. Also, the master node $f_7,$ receives the data from slave nodes $f_5,$ $f_6,$ $f_8,$ and $f_9$. Similarly, the master node $f_{14}$ receives the data from slave nodes $f_{10, }$ $f_{11, }$ $f_{12, }$ and $f_{13}$. While finding the master nodes there may exist the case that, a slave node can communicate with multiple master nodes. We observe that the slave node $f_5$ can establish communication with master nodes $f_4$ or $f_7$. Since the master node $f_7$ shares more number of slave nodes than $f_4,$ we assign $f_5$ to $f_4$. Similarly we assign $f_3$ to $f_4$. If some disturbance occurs in the circuit corresponding to master node $f_4,$ then in emergency master node $f_7$ will take care of $f_5$.

4.   Conclusions

In this paper, the structural properties of very strongly perfect graphs, odd cycles, perfectly orderable, bipartite, and strongly perfect graphs are discussed. We gave an algorithm for the strong independent set on $C_{2k+1}$ or $C_{2k+1}+ e,$ $k \geq 2$ free graphs. We believe that these methods could be used to develop a mathematical model for a real situation, wherein an optimal set of leaders from a given set of people can be chosen. Moreover, in the wireless sensor network, we also extended our techniques to find the optimal set of master nodes that receive the data from all slave nodes and control the given system of the network. The work carried out in this paper will serve as a base for further studies on the remaining graph classes as well.

Conflict of interest

The authors declare that they have no conflicts of interest.