L. Kang, E. Shan, M. Zhao
Domination in the generalized Petersen graphs
Discussiones Mathematicae Graph Theory
Received 31.07.2017, Revised 26.02.2018, Accepted 26.02.2018, doi: 10.7151/dmgt.2137
The problem of monitoring an electric power system by placing as few measurement devices in the system can be formulated as a power dominating set problem in graph theory. The power domination number of a graph is the minimum cardinality of a power dominating set. Xu and Kang [ On the power domination number of the generalized Petersen graphs, J. Comb. Optim. 22 (2011) 282--291] study the exact power domination number for the generalized Petersen graph P(3k,k), and propose the following problem: determine the power domination number for the generalized Petersen graph P(4k,k) or P(ck,k). In this paper we give the power domination number for P(4k,k) and present a sharp upper bound on the power domination number for the generalized Petersen graph P(ck,k).
power domination, domination, generalized Petersen graph, electric power system