OJDM  Vol.9 No.3 , July 2019
Domination and Eternal Domination of Jahangir Graph
Abstract: In the eternal dominating set problem, guards form a dominating set on a graph and at each step, a vertex is attacked. We consider the “all guards move” of the eternal dominating set problem. In which one guard has to move to the attacked vertex and all the remaining guards are allowed to move to an adjacent vertex or stay in their current position after each attack. If the new formed set of guards is still a dominating set of the graph then we successfully defended the attack. Our goal is to find the minimum number of guards required to eternally protect the graph. We call this number the m-eternal domination number and we denote it by . In this paper we find the eternal domination number of Jahangir graph Js,m for s=2,3 and arbitrary m. We also find the domination number for J3,m .
Cite this paper: Shaheen, R. , Assaad, M. and Kassem, A. (2019) Domination and Eternal Domination of Jahangir Graph. Open Journal of Discrete Mathematics, 9, 68-81. doi: 10.4236/ojdm.2019.93008.

[1]   Burger, A.P., Cockayne, E.J., et al. (2004) Infinite Order Domination in Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 50, 179-194.

[2]   Goddard, W., Hedetniemi, S.M. and Hedetniemi, S.T. (2005) Eternal Security in Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 52, 169-180.

[3]   Klostermeyer, W.F. and Mynhardt, C.M. (2016) Protecting a Graph with Mobile Guards. Applicable Analysis and Discrete Mathematics, 10, 1-29.

[4]   Finbow, S., et al. (2015) Eternal Domination in 3 × n Grids. The Australasian Journal of Combinatorics, 61, 156-174.

[5]   Messinger, M.E. and Delaney, A.Z. (2017) Closing the GAP: Eternal Domination on 3 × n Grids. Contributions to Discrete Mathematics, 12, 47-61.

[6]   Mojdeh, D.A. and Ghameshlou, A.N. (2007) Domination in Jahangir Graph J2,m. International Journal of Contemporary Mathematical Sciences, 2, 1193-1199.

[7]   Goldwasser, J., Klostermeyer, W. and Mynhardt, C.M. (2013) Eternal Protection in Grid Graphs. Utilitas Mathematica, 91, 47-64.