Authors: Nathan Klundt, Violeta Vasilevska
Mentors: Violeta Vasilevska
Insitution: Utah Valley University
In electrical power networks, phase measurement units (PMUs) are sensors used to monitor the network. However, these PMUs are very costly, hence the electric company are interested in using the minimum number of PMUs that will ensure that they can observe the whole network. This real-life problem is modeled in graph theory as a graph coloring game. Namely, the power domination problem [2, 3] in graph theory is concerned with finding a minimum number of these sensors needed to color (observe) the entire graph (network) according to a set of rules. We consider two variants of this coloring problem. The k-fault-tolerant power domination [3] is asking to find minimum number of PMUs needed to observe (color) the whole network (graph) even when k number of the PMUs are faulty but allows only one PMU to be placed on an electric node (vertex). The other variant, called robust power domination [1], asks the same as fault tolerant power domination, but allows for multiple PMUs to be placed on the same electric node (vertex). In this presentation, we introduce these coloring problems through examples, and provide some theoretical bounds on the minimum number of PMUs needed for various families of graphs for both k-fault-tolerant and robust power domination problems.
References:
[1] Beth Bjorkman and Esther Conrad. (2023). Introduction to Robust Power Domination.
arXiv:2305.13430.
[2] Dennise J. Brueni and Lenwood S. Heath. The PMU placement problem. SIAM Journal on Discrete Mathematics, 19(3): 744-761, 2005.
[2] Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Michael A. Henning. Domination in graphs applied to electric power networks. SIAM Journal on Discrete Mathematics, 15(4): 519-529, 2002.
[3] Kung-Jui Pai, Jou-Ming Chang, and Yue-Li Wang. Restricted power domination and fault-tolerant power domination on grids, Discrete Applied Mathematics, 158(10):1079–1089, 2010.