Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating function on G. Note that the 1-distance Roman domination number γ1R (G) is the usual Roman domination number γR(G). In this paper, we investigate properties of the k-distance Roman domination number. In particular, we prove that for any connected graph G of order n ≥ k +2, γkR (G) ≤ 4n/(2k +3) and we characterize all graphs that achieve this bound. Some of our results extend these ones given by Cockayne et al. in 2004 and Chambers et al. in 2009 for the Roman domination number.
@article{bwmeta1.element.doi-10_7151_dmgt_1703,
author = {Hamideh Aram and Sepideh Norouzian and Seyed Mahmoud Sheikholeslami},
title = {The Distance Roman Domination Numbers of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {717-730},
zbl = {1305.05171},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1703}
}
Hamideh Aram; Sepideh Norouzian; Seyed Mahmoud Sheikholeslami. The Distance Roman Domination Numbers of Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 717-730. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1703/
[1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications (The Macmillan Press Ltd. London and Basingstoke, 1976). | Zbl 1226.05083
[2] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575-1586. doi:10.1137/070699688[WoS][Crossref] | Zbl 1207.05135
[3] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22. doi:10.1016/j.disc.2003.06.004[Crossref] | Zbl 1036.05034
[4] E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga, and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19-32. | Zbl 1081.05083
[5] O. Favaron, H. Karami and S.M. Sheikholeslami, On the Roman domination number in graphs, Discrete Math. 309 (2009) 3447-3451. doi:10.1016/j.disc.2008.09.043[Crossref] | Zbl 1191.05071
[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. NewYork, 1998). | Zbl 0890.05002
[7] B.P. Mobaraky and S.M. Sheikholeslami, Bounds on Roman domination numbers of a graph, Mat. Vesnik 60 (2008) 247-253. | Zbl 1274.05359
[8] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000) 585-594. doi:10.2307/2589113[Crossref] | Zbl 1039.90038
[9] I. Stewart, Defend the Roman Empire, Sci. Amer. 281 (1999) 136-139.
[10] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000).