EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 1, Article Number 5753 ISSN 1307-5543 – ejpam.com Published by New York Business Global Optimal Placement of PMUs using k-Power Domination Number in Grid Networks J. Anitha1, R. Manimegalai2, S. Nithishkumar2, R. Arthi2, V. Govindan3, Siriluk Donganont4,∗ 1 Department of Mathematics, Rajalakshmi Institute of Technology, Chennai-600 124, Tamil Nadu, India. 2 Department of Computer Science and Engineering, PSG Institute of Technology and Applied Research, Coimbatore-641 062, Tamil Nadu, India. 3 Department of Mathematics, Hindustan Institute of Technology and Science, Chennai, Tamil Nadu, India. 4 School of Science, University of Phayao, Phayao 56000, Thailand. Abstract. The problem of monitoring an electric power system by placing Phasor Measurement Units in the system as possible is closely related to the well-known power domination problem in graphs. In this paper, we compute, 2-power domination number for fully connected cubic networks and also developed k-power domination algorithm for specific networks and evaluates its performance across these networks. Furthermore, the algorithm’s outputs are used for various other applications such as fault detection and localization, state identification, accuracy improve- ment, and cyber security enhancement, thereby making it a valuable tool for utilities and grid operators. 2020 Mathematics Subject Classifications: 05C69, 90B10, 94C15, 68M10, 05C85 Key Words and Phrases: Optimal PMUs Placement, Dominating Set, Facility Location Problem, Electrical Power System, Power Grid Monitoring 1. Introduction Optimal PMUs Placement(OPP) is viewed as an optimization problem. The task is to find the minimum possible set of PMUs to monitor the entire electric power system. An electrical line that connects a pair of electric nodes is represented by each edge in a graphical representation G(V,E) of the electric power network. Every vertex of the network symbolizes an electric node. PMU placement with a view to measuring the state variable for the vertex at which it is place is the goal. It also helps to ensure that the system is running efficiently and that energy is being used in a cost-effective manner, ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i1.5753 Email addresses: anithaharish78@gmail.com (J. Anitha), vgovindandr@gmail.com (V. Govindan), siriluk.pa@up.ac.th (S. Donganont) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 2 of 16 which is calculated by a number of crucial unknowns including the phase angle of ma- chine at generators and the magnitude of the voltage at loads. The concept of k-PD in graphs encapsulates the challenge of achieving comprehensive system monitoring with as few PMUs as possible. Despite recent cost reductions, comprehensive PMU deployment across all electric grid nodes is hampered by several challenges. As per industry proto- cols, PMUs are routinely placed in substations during refurbishment. However, strategic placement of PMUs at key buses is recommended to ensure system observability. Power domination algorithms are used to place PMUs in electrical grid networks in the best possible way to monitor the power system. A subset S ⊆ V in a graph is said to be a dominating set G if every vertex in V is either in S or is adjacent to some vertices in S [11]. In 2002, Hayens et al. [11] considered this problem as the power domination prob- lem in graphs which is a variation of the domination problem. An electric power network is designed by a graph where the vertices represent the electric nodes and the edges are associated with the transmission lines joining two electrical nodes. In 2012, Paul Dorbec et al.[8] presented the idea of k-power domination problem which is a generalization of power domination problem in graphs. The notation for the k-power dominating set is γp,k(G). More extensive conditions are applied to the monitoring of the complete graph G. In order to achieve full observability of the electric power system k-power domination algorithm is employed. This approach not only enhances monitoring efficiency but also offers a cost-effective solution by minimizing the total number of PMUs required, thus overcoming the logistical, financial, and architectural challenges inherent in large-scale PMU deployment. 1.1. Preliminaries and Definitions A path, is a linear network whose nodes are arranged as v1, v2, . . . , vr, with edges of the form {vj , vj+1} where j = 1, 2, . . . , r − 1 . A complete network Kn, in which each pair of unique nodes is connected by a single line. A cycle Cn, forn ≥ 3, contains n edges and n vertices, with the edges forming a loop connecting the vertices in sequence from v1tovn and back to v1. A star network, K1,r, is a tree with r nodes, exacctly one node of degree r − 1, while the other r − 1 nodes of degree 1. A friendship graph, is denoted by Fr, is formed by connecting r number of the cycles C3 with a central node [10]. Binary tree is a tree, each node can have up to two children, typically called the left and right children. The ladder is a Cartesian product of Pr × P2, denoted by Lr,1 . [1]. Cartesian Product of G×H. The following conditions holds: • In the Cartesian product G×H, the vertices (s, t) and (s′, t′) are neighbours only if s = t′ and t is a neighbour to t′ in H, or t = t′ and u is a neighbour to s′ in G. • The vertex set of G×H is given by V (G)× V (H). A graph G = (V,E) is defined as a nonempty set of vertices V = V (G) together with a set of edges E = E(G) joining certain pairs of vertices. Vertices u and v are said to be J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 3 of 16 adjacent if u and v are the end vertices of an edge in G. For u ∈ V , the set of all vertices adjacent to u are said to be in the neighbours of u and is denoted by N(u). Then, the closed neighbourhood of u is defined as N [u] = N(u) ∪ {u}. Dominating Set: A vertex v is represents to as a dominating set over a vertex u if u and v are neighboring vertices in G. If every vertex not in S is adjacent to at least one vertex in S, then set S ⊆ V (G) is called a dominating set. The least size of such a set S is called the domination number of G, denoted by γ(G). k-Power Dominating Set(k-PDS): Given an integer k ≥ 0 and a graph G(V,E), a set S ⊆ V (G) is called a k-PDS if it monitors all vertices in G through inductive step. Define the sets M i(S) of vertices monitored by S at level i as follows: 1. M0(S) = N [S] 2. M i+1(S) = M i(S) ∪ {N(v) : ∃v ∈M i(S), |N(v) \M i(S)| ≤ k}. If M∞(S) = V (G), then the set S is a k-PDS . The γp,k(G), is the minimum size of a k-PDS of G. v1 v2 v3 v4 vn (a) Path Graph, Pn v4 v3 v2 v1 vn (b) Cycle Graph, Cn v4 v3 v2 v1 vn (c) Complete Graph, Kn v0 v1 v2 v3 v4 vn (d) Star Graph, K1,n a1 a2 a3 an b1 b2 b3 bn (e) Ladder Graph, Ln,1 1 2 4 5 3 6 7 (f) Binary Tree, Tn The zero forcing process can be treated as a coloring process on the vertices of the graph. If vertex x is colored red and exactly one neighbor y of x is green, then change the color of y to red and we say that x forces y. A zero forcing set for G is a subset J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 4 of 16 1 2 1 2 1 2 3 4 3 4 3 4 G : (a) (i) (ii) (iii)5 6 7 5 6 7 5 6 7 8 8 1 2 1 2 1 2 3 4 3 4 3 4 G : (b) (i) (ii) (iii)5 6 7 5 6 7 5 6 7 8 8 Figure 2: (a) Vertex in red is a power dominating set in G with γp(G) = 2 (b) Vertex in red is a 2-power dominating set in G with γp(G) = 1 of vertices H such that if initially the vertices in H are colored red and the remaining vertices are colored green, then repeated application of the above process can color all vertices of G red. This concept helps to identify how control can propagate through a network. The cardinality of a minimum zero forcing set of G is represented by ζ(G) [3]. In Figure 1, we illustrate as follows: For the graph G, in Figure 1(a), the vertex labeled 1 marked in red, is a power dominating set. At the first time step, vertex 1 monitors vertex 2 and vertex 3, further propagation not possible from vertices labeled 2 and 3. Now include one more vertex in a power dominating set in vertex labeled as 3, then at the second time step, vertex 3 monitors vertices 5 and 6, vertex 2 monitors vertex 8, and at the third time step, vertex 4 monitors vertex 7. For the same graph G, in Figure 1(b), we determine a 2-power dominating set S as fol- lows: the vertex labeled 1 marked in red is a 2-power dominating set. At the first time step, vertex 1 monitors vertex 2 and vertex 3. At the second time step, vertex 3 monitors vertices 5 and 6, vertex 2 monitors vertex 8. Finally, at the third time step, vertex 4 monitors vertex 7, completing the monitoring process in fewer steps. This demonstrates the efficiency of a 2-power dominating set in reducing the number of monitored steps. 2. Literature review The PD problem is NP -complete . Even when restricted to chordal and bipartite graphs or even split graphs, which are a subclass of chordal graphs and it has been J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 5 of 16 shown to be NP -complete. But in the case of interval graphs, Liao and Lee presented a linear method for this problem, assuming that the graph’s interval ordering is known [15]. In the absence of interval order, they provided an O(nlogn) algorithm, which they demonstrated to be asymptotically optimal. For trees and, more broadly, graphs with bounded treewidth, more effective techniques have been proposed [12]. The PDN of G, γp(G) ≥ 1 [11]. Dorfling and Henning [9] determined the PDN and minimal power dominating sets for grid graphs. Dorbec et al. calculated γp(G) in [3] when G is the lexicographic product of any two path graphs. Subsequently, Barrera and Ferrero found numerous instances in which their upper bounds for γp(G) correspond with the power domination number whether G is a cylinder, a torus, or a generalised Petersen graph [2]. More generally, Zhao, Kang, and G.J. Chang provided upper bounds for γp(G) for an arbitrary graph G [22]. Additional upper bounds have been provided for claw-free graphs [22] and block graphs [21]. Chang et al. [5] present the k-PD, which is a generalization of Power domination(PD) in graphs. The k-PDN is an NP-complete problem as demonstrated by the computation of the problem’s complexity in their work. [5] demonstrates the sharpness of the bound and shows that for any connected graph G of rank n, γPk (G) < n k+2 . Additionally, it is demonstrated that for any (k + 2)-regular graph of rank n, γPk (G) < n k+3 , and the graphs that meet this last restriction are described. The concept of propagation radius is presented by Dorbec et al. [7], defining it as the least number of steps required for the propagation of k PD sets. The propagation radius for a significant range of parameters in Sierpinski graphs Sn is specifically determined in the paper. However, challenges are faced in establishing concise formulas, particularly for Sierpinski graphs Sp n, where 2k + 2 ≥ p ≥ k + 1 + √ k + 1 and n ≥ 3. The computational complexity of failed power domination has been addressed by Glasser et al. [10], highlighting the NP-hardness of power domination computation. The paper focuses on identifying graphs where every vertex acts as its own power dominating set (PDS), contributing a list of such graphs. However, while offering this valuable insight, it fails to explore specific traits and properties of graphs with a PD number of 0, which remains an uncharted domain. Significant progress has been made by Brimkov et al. [4] in exploring connected PD within graphs, with the NP-hardness of determining the domination number in connected graphs being firmly established. NP-completeness of certain graphs has been proven, leading to various structural discoveries. Various structural insights have been provided by their research through the proof of the NP-completeness of specific graphs. Moreover, a formula for the bi-connected components’ numerical values and the graph’s connected PD number have been determined. Despite these successes, attempts to determine the PD of IEEE Bus 300 have run into problems since the calculations have exceeded timeout limits, revealing problems with the scalability of the computations and their practical use. The employment of bounded-tree width dynamic programs to solve the power dom- inating set has been the main focus of Guo et al. [17]. [17] presents a linear-time technique that is streamlined for determining the PD set in trees. Furthermore, it has J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 6 of 16 been shown that the PD set, as defined by |P |, is not more accurately measurable than the dominating set and is W[2]-hard. However, there are still a lot of topics that require additional study. In line with variants of domination and power domination with appli- cations in fuzzy graphs, domination in vague graphs[16], survey on domination in vague graphs with application in transferring cancer patient [14], topological indices in fuzzy graphs [13], vague graphs with novel application[19, 20], abelian covers of the Wreath graph W (3, 2) and the Foster graph F26A[6]. 3. Fully Connected Cubic networks (FCCNs) A fully connected cubic network is a recursive network and is defined as follows[18]: Let Z7 = {0, 1, 2, 3, 4, 5, 6, 7}, and for a ∈ Z7, let a s = aa . . . a(s times), s ≥ 1. For r ≥ 1. An r-level FCCN , denoted by FCCNr, r ≥ 1, is a graph defined inductively as follows: 1. FCCN1 is a network with V (FCCN1) = Z7 and E(FCCN1) = {(0, 1), (0, 2), (1, 3), (2, 3), (4, 5), (4, 6), (5, 7), (6, 7), (0, 4), (1, 5), (2, 6), (3, 7)}. 2. When r ≥ 2, FCCNr is constructed from eight node-distinct copies of FCCNr−1 by connecting additional 28 edges. Particularly, if, for 0 ≤ t ≤ 7, we let tFCCNr−1 denote a copy of FCCNr−1 with each node being prefixed with t, then FCCNr is defined by V (FCCNr) = 7⋃ t=0 V (tFCCNr−1), E(FCCNr) = ( 7⋃ t=0 E(tFCCNr−1)) ∪ {(abr−1, bar−1)|0 ≤ a < b ≤ 7}. For 0 ≤ t ≤ 7, tFCCNr−1 is called an (r− 1)-level sub-FCCN of FCCNr, or simply a sub-FCCN of FCCNr, if there is no ambiguity. 3. Given an FCCNr, r ≥ 2, a boundary node is a node of the form tr. An intercubic edge is an edge of the form (abr−1, bar−1). In essence, each node of an FCCN has four links, with each boundary node having one I\O channel link that is not counted in the node degree. Obviously, tFCCNr−1 has 7 intercubic vertices and 1 boundary vertex for 0 ≤ t ≤ 7 and r ≥ 2 [18]. See Figure 3. 4. 2-PD in Fully Connected Cubic Network(FCCN) In this section, we find the k-PDN, k ≥ 2 for FCCNr, r ≥ 2. The power domination process on a graph G is choosing a set S ⊆ V (G) and applying the zero forcing process to the closed neighborhood N [S] of S. The set S is a power dominating set of G if and only if N [S] is a zero forcing set for G [3]. Rao et al.[22] proved that the bound is tight for fully connected cubic networks. In 2015 Ferrero et al. [3] proved the following theorem which shows the relationship between zero forcing set and power dominating set. Theorem 1. [3] Let G be a graph. Then ⌈ Z(G) ∆(G) ⌉ ≤ γp(G) and this bound is tight. J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 7 of 16 0 1 3 4 6 5 7 2 (b) 00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17 20 21 22 23 24 25 26 27 30 31 32 33 34 35 36 37 40 41 42 43 44 45 46 47 50 51 52 53 54 55 56 57 60 61 62 63 64 65 66 67 70 71 72 73 74 75 76 77 boundary vertex intercubic vertex (a) Figure 3: Fully connected cubic networks (a) FCCN1 (b) FCCN2 with 00, 11, . . . , 77 as boundary vertices In 2022 Anitha et al. [18] proved the following theorem which shows the relationship between zero forcing set and power dominating set described in Theorem 2. Theorem 2. [18] For the FCCN Hr ∼= FCCNr, r ≥ 2, we have γp(Hr) = 23r−4. Theorem 3. [18] For the FCCN Hr ∼= FCCNr, r ≥ 2, we have ζ(Hr) = 23r−2. In this section we solve 2-power domination number for Hn, n ≥ 2 Lemma 4. For FCCN2, we have γp,2(FCCN2) ≥ 2. Proof. FCCN2 contains eight node distinct copies of FCCN1, say 0FCCN1, 1FCCN1, . . . , 7FCCN1. Let S be a 2-PD set of G. We claim that |S| ≥ 2. A node v in G is of the following two categories: (i) v is adjacent to only nodes of degree 4. (ii) v is adjacent to a node of degree 3. Suppose |S| = 1. Then the only node in S cannot be a node of category (i) . Therefore, let S = {u} where u is a boundary node. The neighbours of u are x, y, z, say, in some FCCN1, each of which is adjacent to 2 vertices of the same FCCN1 and one node in three disjoint copies of FCCN1. See Figure 3(b). None of these nodes is adjacent to J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 8 of 16 unmonitored nodes of degree at most 2. Hence |S| ≠ 1. Lemma 5. Let S be a 2-PD set FCCN3. Then |V (FCCN3) ∩ S| ≥ 9. Proof. Let S be a 2-PD set of FCCN3. We claim that |S| ≥ 9. Suppose not, FCCN3 is composed of eight copies of FCCN2, denoted by 0FCCN2, 1FCCN2, . . . , 7FCCN2. Even if, all iFCCN2, 0 ≤ i ≤ 7 contains exactly one node from 2-PD set. A node v ∈ S in G is of the following three categories: (i) v is of degree 3. (ii) v is of degree 4 not adjacent to a node of degree 3. (iii) v is adjacent to a node of degree 3. Suppose |S| = 8. Let S can be a node of category (i) and category (ii). Therefore, let S = {ui : deg(ui) = 3 or deg(ui) = 4} where ui is a boundary node in each FCCN2 or not adjacent to a boundary node. The neighbours of ui are x, y, z, say, in some FCCN1, each of which is adjacent to 2 nodes of the same FCCN1 and one node in three disjoint copies of FCCN1. Further propagation cannot be done. See Figure 1(b). None of these vertices is adjacent to unmonitored vertices of degree at most 2. Hence |S| ≠ 8. Suppose S = {ui : deg(ui) = 4} can be a node of category (iii) in some FCCN1. Then each boundary node is adjacent to two nodes, then the boundary nodes can monitor their neighbouring nodes. Then nodes in M1(S) is adjacent to two nodes in same FCCN1 and one node in three disjoint copies of FCCN1. Further propagation cannot be done. Hence |S| ≠ 8. Thus |S| = 9. Therefore, γp,2(FCCN3) = 9. Lemma 6. For FCCN, n ≥ 3, we have γp,2(FCCNr) ≥ 9× 8r−3. Proof. We prove the result by induction on r. We consider the case when r = 3. H3 has eight node disjoint copies of FCCN2, say FCCN2, 1FCCN2, . . . , 7FCCN2. Let S be a 2-power dominating set of FCCNr. We claim that |S| ≥ 9. By Lemma 5, there are at least one vertex in each copy of FCCN2 and one more additional vertex to monitor FCCN3. Hence |S| ≥ 9. Therefore, γp,2(FCCN3) ≥ 9. Assume the result is true for r = k, r ≥ 3. That is, γp,2(FCCNk) ≥ 9 × 8k−3. Consider the case when r = k+1. Let S be a 2-power dominating set Hk+1. We have to prove that γp,2(FCCNk+1) ≥ 9× 8k−2. Suppose not, let |S| < 9× 8k−2. By definition, there are 8k−2 vertex disjoint copies of FCCN3 in FCCNk+1. With the removal of one node from S in a copy of FCCN2, The neighbours of some u are x, y, z, say, in some FCCN1, each of which is adjacent to 2 nodes of the same FCCN1 and one node in three disjoint copies of FCCN1. Further propagation cannot be done. a contradiction. Thus |S| ≥ 9× 8k−2. Therefore, γp,2(FCCNk+1) ≥ 9× 8k−2. Hence the proof. The Algorithm given below computes the 2-PD for FCCNs FCCNr . 2-PD Algorithm: J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 9 of 16 Input: FCCN FCCNr, r ≥ 3, with radix-lexicographic ordering. Algorithm: (i) Select S3 = {001, 013} ∪ 7⋃ t=1 t10 in FCCN3. (ii) Let S4 = 7⋃ t=0 tS3 in FCCN4. (iii) Inductively select Sr = 7⋃ t=0 tSr−1 in FCCNr. 000 001 002 003 004 005 006 007 010 011 012 013 014 016 017 020 021 022 023 024 025 026 027 030 031 032 033 034 035 036 037 040 041 042 043 044 045 046 047 050 051 052 053 054 055 056 057 060 061 062 063 064 065 066 067 070 071 072 073 074 075 076 077 015 Monitored vertices of unmonitored vertices 00 01 02 03 0 4 05 06 07 10 11 12 13 14 15 16 17 20 21 22 2 3 24 25 26 27 30 31 32 33 34 35 36 37 40 41 42 4 3 44 45 46 47 50 51 52 5 3 54 55 56 57 60 61 62 63 64 65 66 67 70 71 72 73 74 75 76 77 x y z boundary vertex intercubic vertex (a) (b) Figure 4: 0n−2FCCN2 of FCCNr Output: γp,2(FCCNr) = 9× 8r−3 Proof of Correctness: Let Sr be a 2-PD set of FCCNr with |Sr| = 9×8r−3. Let S3 be a 2-PD set of FCCN3. Then M0(S3) = N [S3] = 7⋃ t=0 {000, 005, 003, 010, 013, 031, 011, 017}∪ 7⋃ t=1 {101, 110, 111, 114, 112}. Then M0(S4) = N [S4] = 7⋃ t=0 tM0(S3). Proceeding in- ductively, M0(Sr) = N [Sr] = 7⋃ t=0 tM0(Sr−1) Then nodes inM0(Sr) say, 7⋃ t=0 tr−2S ′′ where S ′′ = {00, 02, 03, 10, 11, 12, 21, 22, 23, 30, 31, 33} is adjacent to exactly two unmonitored vertices say, 7⋃ t=0 tr−2S ′′′ where S ′′′ = {04, 06, 07, 14, 15, 16, 25, 26, 27, 34, 35, 37}. Now M1(Sr) = M0(Sr)∪ 7⋃ t=0 tn−2S ′′′ . Then for every vertex v ∈M1(Sr), |N [v]\M1(Sr)| = 2. rNow M2(Sn) = M1(Sn) ∪ 7⋃ t=0 tn−2ij, 4 ≤ i ≤ 7, 0 ≤ j ≤ 3. Similarly in the next step, M3(Sr) = M2(Sr) ∪ 7⋃ t=0 tr−2ij, 4 ≤ i, j ≤ 7. Proceeding inductively, M3(Sr) = V (FCCNr). Hence the proof. Therefore, γp,2(FCCNr) ≤ 9× 8r−3. J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 10 of 16 The following result is a consequence of Lemma 6 and by 2-PD Algorithm . Theorem 7. For FCCNs FCCNr, r ≥ 3, we have γp,2(FCCNr) = 9× 8r−3. In 2012, Chang et al. [5] obtained the following results for a connected graph G. Theorem 8. If G is connected and ∆(G) ≤ k + 1, then γp,k(G) = 1. The following result is a consequence of Theorem 8 Theorem 9. For FCCNs FCCNr, r ≥ 3, we have γp,k(FCCNr) = 1, k≥ 4. 5. k-PD Algorithm Algorithm PDS($G(V,E),k){ min set← V (G) min set size←∞ vertices← list of all vertices in G for size := 1 to |vertices| { for each subset S ⊆ vertices with |S| = size { monitored← S ∪ (⋃ v∈S N(v) ) new monitored← monitored while True { to add← ∅ for each vertex v ∈ monitored { neighbors← N(v) unmonitored neighbors← neighbors \monitored if |unmonitored neighbors| ≤ k { to add← to add∪unmonitored neighbors } } if to add = ∅ { break } new monitored← new monitored ∪ to add monitored← new monitored } if |monitored| = |V (G)| { if |S| < min set size { min set← S min set size← |S| } } } } return min set } =0 J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 11 of 16 (a) Comb graph P+ 6 (b) Binary tree T3 (c) Sibling tree ST 1 3 Figure 6: Power Dominating Set in Comb Graph, Binary Tree and Sibling Tree using Power Domination Algorithm (a) Path graph P16 (b) Cycle graph C16 (c) Complete graph K16 (d) Star graph K1,15 (e) Fan graph F5 (f) Ladder graph L6 Figure 5: k-Power Dominating Set in Different Types of Graph Networks using k-Power Domination Algorithm The PDS algorithm identifies the k-power domination set, depicted by red vertices in the pictures above, as the smallest subset of nodes required for full network observabil- ity. The k-power domination set is deliberately placed in each graph to provide optimal coverage, whether along linear lines, across cyclic structures, at central hubs and out- lying nodes, or scattered across multiple layers, improving power system reliability and J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 12 of 16 (a) Comb graph P+ 6 (b) Binary tree T3 (c) Sibling tree ST 1 3 Figure 7: 2-Power Dominating Set in Comb Graph, Binary Tree and Sibling Tree using 2-Power Domination Algorithm stability. For binary, sibling, and comb graphs, the power domination algorithm differs significantly from the 2-power domination algorithm, which adds redundancy. However, for other graphs, both k=1 and k=2 yield the same result, demonstrating that the small- est subset is sufficient for comprehensive coverage. Table 1 shows the execution time to compute the k-PDS for various types of graphs with 16 nodes Type of Graph Execution time k=1 k=2 Path Pn 1.018 1.020 Cycle Cn 0.980 0.945 Ladder Ln 0.866 0.929 Complete graph Kn 0.971 0.950 Star Graph K1,n 1.010 1.085 Fan graph Fn 0.131 0.129 Comb graph P+ n 0.415 0.447 Binary tree Tn 1.85 2.12 Sibling tree ST 1 n 0.477 0.379 Table 1: Execution Time to Compute the k-Power Dominating Set for Graphs with 16 Nodes 5.1. Optimal PMU Placement (OPP) The proposed k-power domination algorithm is a highly efficient and robust solu- tion for OPP in electrical grid systems. It ensures comprehensive network observability by identifying a minimal subset of nodes where PMUs should be placed, thereby guar- anteeing that each node in the grid is monitored either directly or indirectly. This approach not only minimizes the number of PMUs required but also maximizes cover- age, enhancing the reliability and stability of the electric grid. Unlike traditional greedy algorithms, which often necessitate more PMUs to achieve full observability and may J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 13 of 16 not always yield minimal sets, the k-power domination algorithm provides a precise and minimal solution. Compared to Integer Linear Programming (ILP) methods, which can be computationally intensive and impractical for large-scale networks, this algorithm is computationally efficient and scalable, making it suitable for various grid topologies and sizes. Moreover, the k-PD algorithm incorporates the concept of k-redundancy, ensuring that each node is observed by multiple PMUs, which significantly improves fault toler- ance and robustness against failures. This redundancy guarantees continuous monitoring and control even in the event of PMU malfunctions. The algorithm’s flexibility allows it to adapt to dynamic changes in network topology, such as the addition or removal of nodes, ensuring sustained optimal performance in evolving grid environments. In terms of cost efficiency, the k-PD algorithm reduces the overall number of PMUs needed, thereby lowering implementation and maintenance costs. By optimizing PMU placement to minimize overlap and maximize observability, it ensures operational ef- ficiency and effective data collection. Its proven effectiveness in various studies and real-world applications highlights its practical applicability, making it a preferred choice for grid operators aiming to enhance monitoring and control of electric grids. Overall, the k-power domination algorithm represents a superior method for PMU placement, addressing the limitations of other approaches and significantly contributing to the reli- ability, stability, and efficiency of power systems. The following Table II depicts the cost of placement of PMUs in electric grid networks by implementing k-power domination algorithm. Type of Network Heuristic methods PDS Algorithm k = 1 k = 2 Path Pn 300000 50000 50000 Cycle Cn 300000 50000 50000 Ladder Ln 250000 50000 50000 Complete graph Kn 50000 50000 50000 Star Graph K1,n 50000 50000 50000 Fan graph Fn 50000 50000 50000 Comb graph P+ n 300000 100000 50000 Binary tree Tn 350000 200000 50000 Sibling tree ST 1 n 250000 200000 50000 Table 2: Cost of placement of PMUs using Various Strategies(in dollars) The Table II shows costs associated with placing Phasor Measurement Units (PMUs) using heuristic methods and the Power Dominating Set (PDS) algorithm across various network topologies. It demonstrates that the PDS algorithm is generally more cost- effective than heuristic methods. For Path pn, Cycle Cn, Ladder Ln, and Comb graph P+ n , the heuristic method costs higher compared to the PDS algorithm’s $50,000. This trend is similar for Binary Tree (Tn) and Sibling Tree (ST) topologies, where the heuris- tic methods cost $350,000 and $250,000 respectively, while the PDS algorithm costs J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 14 of 16 $200,000. For k = 2, both methods generally show similar costs, around $50,000, ex- cept for Binary Tree (Tn) and Sibling Tree (ST), where the heuristic methods still have higher costs compared to the PDS algorithm’s $50,000. This analysis indicates that the PDS algorithm effectively reduces the cost of PMU placement, especially for more complex or larger networks, by optimizing the number and placement of PMUs needed for comprehensive system observability. 6. Conclusions In this paper, the PD algorithm is used to improve grid monitoring and control systems. The scalability of the PD and 2-PD algorithm is tested for various graph structures. Despite challenges with specific configurations such as ladder graphs, the algorithm demonstrates its effectiveness in graphical networks and adaptability to struc- tural context. This adaptability is important for real-world applications, where power grids often have complex and heterogeneous structures. PMUs play a important role by providing accurate and timely measurements of voltage and current. Network oper- ators gain comprehensive, real-time information about system status, allowing them to respond to incidents and errors more effectively by strategically placing PMUs in key locations. Acknowledgements: We sincerely appreciate the editors and anonymous reviewers for their insightful suggestions, which greatly enhanced the quality of this paper. Funding: This research was supported by University of Phayao and Thailand Science Research and Innovation Fund (Fundamental Fund 2025, Grant No. 5020/2567). Declaration of competing interest: The author confirms the absence of any known financial conflicts of interest or personal relationships that might have influenced the work presented in this paper. Availability of data and materials: Not applicable. Author’s Contribution: All authors made equal contributions to the manuscript, participated in its drafting and revision, and approved the final version. Ethical approval: Not applicable. References [1] J. Anitha and Indra Rajasingh. Power domination parameters in hypermesh- pyramid networks and corona graphs. International Journal of Pure and Applied Mathematics, 109(5):59–66, 2016. [2] R. Barrera and D. Ferrero. Power domination in cylinders, tori, and the generalized petersen graphs. Networks, pages 43–49, 2009. J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 15 of 16 [3] K.F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevskak, and B. Wissman. Zero forcing and power domination for graph products. https://arxiv.org/abs/1510.02421. [4] B. Brimkov, D. Mikesell, and L. Smith. Connected power domination in graphs. J. Comb. Optim., 38(1):292–315, 2019. [5] G.J. Chang, P. Dorbec, M. Montassier, and A. Raspud. Generalized power domi- nation of graphs. Discrete Applied Mathematics, 160(12):1691–1698, 2012. [6] Zhihua Chen, S. Kosari, S. Omidi, N. Mehdipoor, A.A. Talebi, and H. Rashmanlou. Elementary abelian covers of the wreath graph w(3,2) and the foster graph f26a. AKCE Int. J. Graphs Comb., 20:20–28, 2022. [7] P. Dorbec and S. Klazvar. Generalized power domination: Propagation radius and sierpinski graphs. Acta Applicandae Mathematicae, 2014. [8] P. Dorbec, M. Mollard, S. Klavzar, and S. Spacapan. Power domination in product graphs. SIAM Journal on Discrete Mathematics, 22(2):554–567, 2008. [9] M. Dorfling and M. Henning. A note on power domination problem in graphs. Discrete Applied Mathematics, 154(6):1023–1027, 2006. [10] J. Guo, R. Niedermeier, and D. Raible. Improved algorithms and complexity results for power domination in graphs. Algorithmica, 52:177–202, 2008. [11] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning. Power dom- ination in graphs applied to electrical power networks. SIAM Journal on Discrete Mathematics, 15(4):519–529, 2002. [12] J. Kneis, D. Mölle, S. Richter, and P. Rossmanith. Parameterized power domination complexity. Inform. Process. Lett., 98(4):145–149, 2006. [13] S. Kosari, X. Qiang, J. Kacprzyk, Q.T. Ain, and H. Rashmanlou. A study on topological indices in fuzzy graphs with application in decision making problems. Journal of Multiple-valued Logic and Soft Computing, 2024. [14] S. Kosari, Z. Shao, Y. Rao, X. Liu, R. Cai, and H. Rashmanlou. Some types of domination in vague graphs with application in medicine. Journal of Multiple-valued Logic and Soft Computing, 2022. [15] C.S. Liao and D.T. Lee. Power domination problems in graphs. Lecture note in computer science, 3595:818–828, 2005. [16] Xiaoli Qiang, Maryam Akhoundi, Zheng Kou, Xinyue Liu, and Saeed Kosari. Novel concepts of domination in vague graphs with application in medicine. Mathematical Problems in Engineering, page 1–10, 2021. [17] R. Sundara Rajan, J. Anitha, and Indra Rajasingh. 2-power domination in certain interconnection networks. Procedia Computer Science, 57:738–744, 2015. [18] Y. Rao, S. Kosari, J. Anitha, I. Rajasingh, and H. Rashmanlou. Forcing parameters in fully connected cubic networks. Mathematics, 10:1263, 2022. [19] Z. Shao, S. Kosari, Y. Rao, H. Rashmanlou, and F. Mofidnakhaei. New kind of vague graphs with novel application. Journal of Multiple-valued Logic and Soft Computing, 40:323–342, 2024. [20] Z. Shao, Y. Rao, S. Kosari, H. Rashmanlou, and F. Mofidnakhaei. Certain notions of regularity in vague graphs with novel application. Journal of Multiple-valued J. Anitha et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5753 16 of 16 Logic and Soft Computing, 2022. [21] G.J. Xu, L.Y. Kang, E.F. Shan, and M. Zhao. Power domination in block graphs. Theoretical Computer Science, 359:299–305, 2006. [22] M. Zhao, L. Kang, and G.J. Chang. Power domination in grid graphs. Discrete Mathematics, 306:1812–1816, 2006.