Double power domination in graphs

Jose, Gisha Marin; Geetha, K. N.; Somasundaram, K.

doi:10.47974/JDMSC-2221

Open Access Research Article

Double power domination in graphs

^*Gisha Marin JoseCorresponding authormj_gisha@cb.students.amrita.eduDepartment of MathematicsAmrita School of Physical SciencesAmrita Vishwa VidyapeethamCoimbatore, Tamil Nadu, 641112, India0009-0008-9526-9702View full profile → , K. N. Geethakn_geetha@blr.amrita.eduDepartment of MathematicsAmrita School of EngineeringAmrita Vishwa VidyapeethamBangalore, Karnataka, 560035, IndiaView full profile → , K. Somasundarams_sundaram@cb.amrita.eduDepartment of MathematicsAmrita School of Physical SciencesAmrita Vishwa VidyapeethamCoimbatore, Tamil Nadu, 641112, IndiaView full profile →

* Corresponding author · click or hover a name for details

pp. 2261–2278Vol. 28Issue 6September 2025DOI: 10.47974/JDMSC-2221 Crossmark XML

Received:: 10 Jul 2024
Published Online:: 15 Sep 2025
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2221
Pages:: 2261–2278

Abstract

Monitoring an electrical network using minimal measurement devices is a problem that led to the study of power domination in graphs. The power domination number of paths or cycles is one. As a result, a single-phase measuring unit (PMU) keeps track of all the vertices of a path or cycle in circuits. When the single connected PMU in a path or circle is not functioning effectively under unexpected conditions, then the observability of the electrical network diminishes. To overcome this problem, Double Power Domination was introduced. A subset 𝒮 of the vertex set of a graph G is called a double power dominating set if every vertex in G is monitored at least twice by the vertices in 𝒮. The minimal cardinality of all double power dominating sets 𝒮 is known as the double power domination number and is symbolized by γDP (G). In this article, we have proposed an algorithm to obtain the double power domination number for any graph. We have related the double power domination number and power domination number. We have demonstrated that the difference between the power domination number and the double power domination number is minimal.

Keywords

Double power domination Power domination Feasible neighborhood set Feasible region Propagation depth PMU placement

Subject Classifications

05C6905C12

References

[1] T. L. Baldwin, L. Mili, M. B. Boisen, and R. Adapa, “Power system observability with minimal phasor measurement placement,” IEEE Transactions on Power systems, vol. 8, no. 2, pp. 707–715 (1993).
[2] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning, “Domination in graphs applied to electric power networks,” SIAM journal on discrete mathematics, vol. 15, no. 4, pp. 519–529 (2002).
[3] G. M. Jose and K. N. Geetha, “A contemporary technique to place pmu in an electrical power network using graph theory,” in Proceedings of the 2023 Fifteenth International Conference on Contemporary Computing, pp. 598–602 (2023).
[4] C. Bozeman, B. Brimkov, C. Erickson, D. Ferrero, M. Flagg, and L. Hogben, “Restricted power domination and zero forcing problems,” Journal of Combinatorial Optimization, vol. 37, pp. 935–956 (2019).
[5] M. Dorfling and M. A. Henning, “A note on power domination in grid graphs,” Discrete Applied Mathematics, vol. 154, no. 6, pp. 1023–1027 (2006).
[6] M. Zhao, L. Kang, and G. J. Chang, “Power domination in graphs,” Discrete mathematics, vol. 306, no. 15, pp. 1812–1816 (2006).
[7] P. Bose, V. Gledel, C. Pennarun, and S. Verdonschot, “Power domination on triangular grids with triangular and hexagonal shape,” Journal of Combinatorial Optimization, vol. 40, no. 2, pp. 482–500 (2020).
[8] C. Wang, L. Chen, and C. Lu, “k-power domination in block graphs,” Journal of Combinatorial Optimization, vol. 31, no. 2, pp. 865–873 (2016).
[9] G. Xu, L. Kang, E. Shan, and M. Zhao, “Power domination in block graphs,” Theoretical computer science, vol. 359, no. 1-3, pp. 299–305 (2006).
[10] G. J. Chang, P. Dorbec, M. Montassier, and A. Raspaud, “Generalized power domination of graphs,” Discrete applied mathematics, vol. 160, no. 12, pp. 1691–1698 (2012).
[11] S. Varghese and A. Vijayakumar, ““studies on the power domination problem in graphs,” Ph.D. dissertation, Cochin University of Science and Technology (2016).
[12] I. Yuliana, I. H. Agustin, and D. A. R. Wardani, “On the power domination number of corona product and join graphs,” Journal of Physics: Conference Series, vol. 1211, no. 1, p. 012020 (2019).
[13] M. Bhanumathi and R. M. Abirami, “Upper eccentric domination in graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 22, no. 5, pp. 835–846 (2019).
[14] K. M. Koh and K. W. Soh, “Power domination of the cartesian product of graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 13, no. 1, pp. 22–30 (2016).
[15] K. Soh and K. Koh, “Recent results on the power domination numbers of graph products,” New Zealand Journal of Mathematics, vol. 48, pp. 41–53 (2018).
[16] J. Guo, R. Niedermeier, and D. Raible, “Improved algorithms and complexity results for power domination in graphs,” Algorithmica, vol. 52, pp. 177–202 (2008).
[17] S. T. Hedetniemi, A. A. McRae, and R. Mohan, “Algorithms and complexity of power domination in graphs,” Structures of Domination in Graphs, pp. 461–484 (2021).
[18] B. Brimkov, D. Mikesell, and L. Smith, “Connected power domination in graphs,” Journal of Combinatorial Optimization, vol. 38, pp. 292–315 (2019).
[19] P. Goyal and B. Panda, “Hardness results of connected power domination for bipartite graphs and chordal graphs,” in Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings 15. Springer, pp. 653–667 (2021).
[20] R. Prabha and B. Thenmozhi, “Global power domination of graphs,” Journal of Physics: Conference Series, vol. 1770, no. 1, p. 012065 (2021).
[21] K. Anjana, A. Dinesh, and P. Manjusha, “Global domination number of squares of certain graphs,” Turkish Journal of Computer and Mathematics Education, vol. 12, no. 13, pp. 1980–1986 (2021).
[22] K.-J. Pai, J.-M. Chang, and Y.-L.Wang, “Restricted power domination and fault-tolerant power domination on grids,” Discrete applied mathematics, vol. 158, no. 10, pp. 1079–1089 (2010).
[23] L. Girish and K. Somasundaram, “Bound for the k-fault-tolerant power-domination number,” Symmetry, vol. 16, no. 7, p. 781 (2024).
[24] A. Glasser, B. Jacob, E. Lederman, and S. Radziszowski, “Failed power domination on graphs,” arXiv preprint arXiv:1909.02057 (2019).
[25] F. Harary and T. W. Haynes, “Double domination in graphs,” Ars combinatoria, vol. 55, pp. 201–213 (2000).
[26] T. W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of domination in graphs. CRC press (1998).
[27] A. Cabrera-Martínez and J. A. Rodríguez-Velázquez, “A note on double domination in graphs,” Discrete Applied Mathematics, vol. 300, pp. 107–111 (2021).
[28] P. Nayana and R. R. Iyer, “An algorithm to find a dominating set that secures any connected graph g,” in 2022 IEEE 4th Ph.D. Colloquium on Emerging Domain Innovation and Technology for Society (Ph.D. EDITS). IEEE, pp. 1–2 (2022).
[29] A. Bashian, M. Assili, and A. Anvari-Moghaddam, “A security-based observability method for optimal pmu-sensor placement in wams,” International Journal of Electrical Power & Energy Systems, vol. 121, p. 106157 (2020).
[30] C. Lu, Z. Wang, M. Ma, R. Shen, and Y. Yu, “An optimal pmu placement with reliable zero injection observation,” IEEE Access, vol. 6, pp. 54 417–54 426 (2018).
[31] M. Saravanan, R. Sujatha, R. Sundareswaran, and M. S. Balasubramanian, “Application of domination integrity of graphs in pmu placement in electric power networks,” Turkish Journal of Electrical Engineering and Computer Sciences, vol. 26, no. 4, pp. 2066–2076 (2018).
[32] J. A. Momoh, Y. Xia, and G. Boswell, “Voltage stability enhancement using phasor measurement unit (pmu) technology,” in 2008 40th North American Power Symposium. IEEE, pp. 1–6 (2008).
[33] X.-C. Guo, C.-S. Liao, and C.-C. Chu, “Enhanced optimal pmu placements with limited observability propagations,” IEEE Access, vol. 8, pp. 22 515–22 524 (2020).
[34] T. W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of domination in graphs. CRC press (2013).
[35] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, Topics in domination in graphs. Springer, vol. 64 (2020).
[36] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, “Fundamentals of domination,” in Domination in Graphs: Core Concepts. Springer, pp. 27–47 (2023).
[37] C.-S. Liao and D.-T. Lee, “Power domination problem in graphs,” in Computing and Combinatorics: 11th Annual International Conference, COCOON 2005 Kunming, China, August 16–19, 2005 Proceedings 11. Springer, pp. 818–828 (2005).

Views: 314Downloads: 119Citations: 0