Power Domination in Different Graphs with Applications

Euler was the first to introduce the concept of graph theory in 1736.A graph can be used to represent information about object relationships. Vertices, relations, and edges are used to represent the items. In recent years, there has been a surge in interest in Graph theory.

Because of its wide range of applications in domains including engineering, social science, and biology, graph theory has grown in prominence. A new idea in graph theory has been discovered by a group of mathematicians. Labeling, coloring, and dominance are novel concepts that are beneficial to all fields.

The difficulty of monitoring an electric power system with the fewest available measurement equipment is similar to the well-known domination problem in graphs. Considered this problem's graph theoretical representation as a version of the domination problem in 1998.

Yang et al. [1] produced some wheel-related graphs. Subbulakshmi and Valliammal [2], discuss the transformation of wheel graphs into stars. Chang and Liu [3] establish Cartesian Products of Some Regular Graphs. Akram et.al. [4, 5] established vague hyper graphs. Degree of vertices and regularity in vague graphs discussed Borzooei and Rashmanlou [6] and Borzooei et al. [7].

Chang et al. [8] produced power dominance graphs. Bounds on eigenvalues and chromatic numbers was introduced by Cao [9]. Dean [10] introduced power dominating sets of hypercubes, and Dorfling and Henning [11] discovered power domination in grid graphs Excellent domination in fuzzy graphs discusses Dharmalingam and Nithya [12]. Vague sets develop Gau and Buehrer [13], Yang and Zhang [14] established the independent domination number of the strong product of two cycles. Domination in the join of fuzzy incidence graphs developed Nazeer et al. [15]. In fuzzy graphs, Ismayil and Begum [16] have also displayed dominance.

Fuzzy Graph defines and classifies Karunambigai et.al [17]. The wheel-based cartesian product was investigated by Koh and Soh [18], Soh and Koh [19] and various wheel based Power Domination Number in this described idea of cyclic cartesian product by Liao and Lee [20] establish the power dominance of Sunlet graph and their ways of monitoring electrical power systems Saibavani and Parvathi [21, 22].

In Fuzzy graphs, Paired domination in fuzzy graphs was used to investigate by Manjusha and Sunitha [23, 24] Whitehead and Russel [25] established the cartesian product in graphs, and in two graphs, the cartesian product's dominance number and it's developed the problem in PMU, which Haynes et al. [26] described as a graph modelling problem.

Vague Graphs are defined by Rao et al. [27], the radius of graphs is discussed by Yu et al. [28]. The concept of approximation reasoning was created by Zadeh [29].

Electrical power companies must evaluate the status of their systems on a regular basis, as described by the characteristics. It is defined as the magnitude of voltage at loads and the device phase angle at generators. The most important part of the monitoring strategy is to maintain track of all edges and vertices using the process developed in the Phase Measurement Unit (PMU).

The task of finding the fewest number of PMUs to monitor the entire system is a graph theory problem similar to the well-known vertex covering and domination problems. As a result, this subject is of interest not just to the power system sector, but also to graph theory as a new challenge. For a more in-depth look at the problem of domination and associated subsets.

While dominance has been studied extensively, power dominance has only lately been introduced and examined, in particular, demonstrated that the power dominance problem is NP-complete even when constrained to bipartite or chordal graphs, and offered a linear algorithm for solving the PDS for trees.

The difficulty of finding the smallest collection of PMUs to monitor the entire network is analogous to the well-known vertex coverage and dominance problems in graph theory.

Let G = (V, E) be a graph representing an electric power system, with each vertex representing an electrical node (a substation bus that connects transmission lines, loads, and generators) and each edge representing a transmission line connecting two electrical nodes. The task of finding the fewest number of PMUs to monitor the entire system is a graph theory problem similar to the well-known vertex covering and domination problems. The state variable (voltage and phase angle) for the vertex at which it is situated, as well as its incident edges and end vertices, is measured by a PMU (these vertices and edges are said to be observed.)

Electric utilities must constantly monitor the condition of their systems, which is characterized by a set of state variables. Placing phase measuring units (PMUs) at strategic spots throughout the system is one way to keep track of these factors. Due to the high cost of a PMU, it is preferable to keep the number of PMUs to a minimum while yet being able to monitor (observe) the entire system. When all of the state variables of a system can be determined from a set of measurements, the system is said to be observed.

Definition 3.1

Let G = (V, E) be a graph. A set S of vertices of G is a dominating set (DS) of G if each node of V(G)-S is adjacent to other node in S. A DS S of G is referred to as minimal DS in no proper subset of S is a DS.

Definition 3.2

A minimum DS in a graph $G$  is a DS of minimum cardinality. The cardinality of a minimum DS is called the domination number (DN) of G and is denoted by γ(G).

Definition 3.3

A set D of vertices of G is a strong DN of G if every vertex of V(G)-D is a strong neighbor of other vertex in D.

Definition 3.4

A minimum strong DS as a strong DS of minimum scalar cardinality. The scalar cardinality of a minimum strong DS is called the strong domination number of G.

Definition 3.5

A set S⊂V(G) is said to be a power domination set (PDS). If each vertex and each edge in G(V, E) observes by the vertices in PDS. The minimum cardinality of the PDS is called Power Domination Number $\gamma_P(G)$ .

Theorem 3.1

If G=(V, E) is a strengthened graph, then equal number of vertices of PDSs of G having equal value.

Proof:

Assume that G=(V, E) is a strengthened graph. Then every edge of G is strong edge. If possible, let (m₁₁,m₂₂) be an edge of G which is not strong edge. Then equal number of vertices PDSs of G having equal weight. But G is not a strengthened graph, which is a contradiction. Hence allPDSs of G having equal weight. We wanted to locate as many respiration cylinder companies as conceivable in order to save cash and time. Assume there are four distinct oxygen engine stores in a city that stockpile oxygen cylinders to health centers.

Example 3.1

Consider Figure 1 For the graph G=(V, E).

11.png

Figure 1. Strengthened graph

Theorem 3.2

Let G = (V, E) be a graph, and $\gamma_P(G)=0$  if c only includes one strong arc.

Proof:

Assume G=(V, E) as a graph. If c includes only one strong arc, then γ_P(G)=0. Conversely suppose that γ_P(G)=0. To prove that G contains only one strong arc. If possible, G contains more than one strong arc, then γ_P(G)≠0. which is a contradiction. Hence G contains only one strong arc.

Theorem 3.3

Let G = (V, E) be a graph and if G is Complete Graph then all PDSs of G have equal value.

Proof:

Assume that $G$ is Complete Graph. Then by the definition of Complete Graph, $\mu_2\left(m_{11}, m_{22}\right)=$ $\min \left(\mu_1\left(m_{11}\right), \mu_1\left(m_{22}\right)\right)$ for every $m_{11}, m_{22} \in V$. Suppose $G$ has at least one weak $\left(m_{11}, m_{22}\right)$ edge then, $\mu_2\left(m_{11}, m_{22}\right)<$ $\min \left(\mu_1\left(m_{11}\right), \mu_1\left(m_{22}\right)\right)$ and which implies that $\mu_2\left(m_{11}, m_{22}\right)<\min \left(\mu_1\left(m_{11}\right), \mu_1\left(m_{22}\right)\right) \quad, \quad$ for some $m_{11}, m_{22} \in V$. This contradicts our assumption that $G$ is Complete Graph. Hence all PDSs have equal value.

Example 3.2

Consider Figure 2 For the graph G=(V, E).

2.png

Figure 2. Graphs of PDS

Theorem 3.4

Let G be an graph and if G having at most two non strong arcs, then G contains PDS.

Proof:

Assume G to be a graph. If G having at most two non strong arcs, then G contains PDS.

Conversely, suppose that G contains PDS. To prove that G having at most two non strong arcs. If possible, G contains more than two non strong arcs, then G does not contain a PDS, which is a contradiction. Hence G having at most two non strong arcs.

Example 3.3

Consider Figure 3 For the graph G = (V, E).

3.png

Figure 3. Graphs of PDN

Theorem 3.5

Let G be a graph with power dominate edges. If S is a minimal PDS, then V-S is a PDS.

Proof:

Let S be a minimal PDS of G. Assume V-S is not PDS. Then there exists a vertex to x $x \in S$ S such an extent that x  is not power dominated by anyone vertex in V-S. Since G has power dominate edges, x is a power dominate of somewhere around one vertex in S-{x}. Then S-{x} is a PDS, which contradicts the minimality of S Subsequently, every vertex in S is a power dominate of no less than one vertex in V-S. Hence V-S is a PDS.

Example 3.4

Consider Figure 4 for the graph G=(V, E).

4.png

Figure 4. Graph of PDS

Theorem 3.6

A graph G=(V, E) as even cycle is both PRG and TPRG then G contains PDN.

Proof:

Let G=(V, E) be a PRG. Then its graph G as even cycle and G be both PRG and TPRG. Here are two cases that arise.

Case (i)

Let G be both PRG and TPRG with stable values in V and E. In G all arcs are strong and some PDSs of G having equal number of vertices. Then by the 2.5 definition G contains PDN.

Example 3.5

Let G_PR be both PRG and TPRG with the vertices e₁₁,f₁₁,g₁₁,h₁₁ and edges (e₁₁,f₁₁),(e₁₁,h₁₁),(f₁₁,g₁₁),(g₁₁,h₁₁). Here all arcs are strong.

Case (ii)

Let G be both PRG and TPRG with stable values in V and with equal alternative values in E. In G all arcs are strong and some PDSs of G having equal number of vertices. Then by the 2.5 definition G contains PDN.

Example 3.6

In Figure 5, let G be both PRG and TPRG with the vertices e₁₁,f₁₁,g₁₁,h₁₁ and edges (e₁₁,f₁₁),(e₁₁,h₁₁),(f₁₁,g₁₁),(g₁₁,h₁₁). Here all arcs are strong.

5.png

Figure 5. PRG and TPRG with PDN

From Figure 4 and 5, Let G have n vertices and n edges. Since G is a connected graph, it has a spanning tree T with n vertices and n-1 edges. Let e be the edge not in T, with its endpoints u and v. There is a unique path γ between u and v in T (since T is a tree). The union of e and γ is a cycle. Suppose that there is some other cycle δ. If δ does not contain e, then it is contained in T, contradicting that T has no cycles. If δ does contain e, write it as the union of e and a path in T. Then it is a path from u to v. But γ is the only path from u to v in T.