Geodesic
Power Domination in the Generalized Petersen Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 695-712.

Voir la notice de l'article provenant de la source Library of Science

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).
Keywords: power domination, domination, generalized Petersen graph, electric power system 
@article{DMGT_2020_40_3_a0,
     author = {Zhao, Min and Shan, Erfang and Kang, Liying},
     title = {Power {Domination} in the {Generalized} {Petersen} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {695--712},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a0/}
}
TY  - JOUR
AU  - Zhao, Min
AU  - Shan, Erfang
AU  - Kang, Liying
TI  - Power Domination in the Generalized Petersen Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 695
EP  - 712
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a0/
LA  - en
ID  - DMGT_2020_40_3_a0
ER  - 
%0 Journal Article
%A Zhao, Min
%A Shan, Erfang
%A Kang, Liying
%T Power Domination in the Generalized Petersen Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 695-712
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a0/
%G en
%F DMGT_2020_40_3_a0
Zhao, Min; Shan, Erfang; Kang, Liying. Power Domination in the Generalized Petersen Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 695-712. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a0/

[1] R. Barrera and D. Ferrero, Power domination in cylinders, tori, and generalized Petersen graphs, Networks 58 (2011) 43–49. doi:10.1002/net.20413

[2] A. Behzad, M. Behzad and C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Math. 308 (2008) 603–610. doi:10.1016/j.disc.2007.03.024

[3] D.J. Brueni and L.S. Heath, The PMU placement problem, SIAM J. Discrete Math. 19 (2005) 744–761. doi:10.1137/S0895480103432556

[4] P. Dorbec, M. Mollard, S. Klavžar and S. Špacapan, Power domination in product graphs, SIAM J. Discrete Math. 22 (2008) 554–567. doi:10.1137/060661879

[5] J. Fox, R. Gera and P. Stǎnicǎ, The independence number for the generalized Petersen graphs, Ars Combin. 103 (2012) 439–451.

[6] J. Guo, R. Niedermeier and D. Raible, Improved algorithms and complexity results for power domination in graphs, Lecture Notes in Comput. Sci. 3623 (2005) 172–184. doi:10.1007/11537311_16

[7] T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, and M.A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math. 15 (2002) 519–529. doi:10.1137/S0895480100375831

[8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[9] W.K. Hon, C.S. Liu, S.L. Peng and C.Y. Tang, Power domination on block-cactus graphs, in: The 24th Workshop on Combinatorial Mathematics and Computation Theory (2007) 280–284.

[10] C.S. Liao and D.T. Lee, Power domination problem in graphs, Lecture Notes in Comput. Sci. 3595 (2005) 818–828. doi:10.1007/11533719_83

[11] C.S. Liao and D.T. Lee, Power domination in circular-arc graphs, Algorithmica 65 (2013) 443–466. doi:10.1007/s00453-011-9599-x

[12] K.J. Pai, J.M. Chang and Y.L. Wang, A simple algorithm for solving the power domination problem on grid graphs, in: The 24th Workshop on Combinatorial Mathematics and Computation Theory (2007) 256–260.

[13] Y.L. Wang and G.S. Huang, An Algorithm for Solving the Power Domination Problem on Honeycomb Meshes (Master Thesis, Department of Computer Science and Information Engineering, National Chi Nan University, 2009).

[14] H.L. Wang, X.R. Xu, Y.S. Yang and K. Lü, On the distance pair domination of generalized Petersen graphs P (n, 1) and P (n, 2), J. Comb. Optim. 21 (2011) 481–496. doi:10.1007/s10878-009-9266-1

[15] G. Xu, L. Kang, E. Shan and M. Zhao, Power domination in block graphs, Theoret. Comput. Sci. 359 (2006) 299–305. doi:10.1016/j.tcs.2006.04.011

[16] G. Xu and L. Kang, On the power domination number of the generalized Petersen graphs, J. Comb. Optim. 22 (2011) 282–291. doi:10.1007/s10878-010-9293-y

[17] H. Yan, L. Kang and G. Xu, The exact domintion number of the generalized Petersen graphs, Discrete Math. 309 (2009) 2596–2607. doi:10.1016/j.disc.2008.04.026

[18] B. Zelinka, Domination in generalized Petersen graphs, Czechoslovak Math. J. 52 (2002) 11–16. doi:10.1023/A:1021759001873

[19] M. Zhao, L. Kang and G.J. Chang, Power domination in graphs, Discrete Math. 306 (2006) 1812–1816. doi:10.1016/j.disc.2006.03.037