Geodesic
The Distance Roman Domination Numbers of Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 717-730.

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

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 ω (f) =∑_v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γ_R^k (D), equals the minimum weight of a k-distance Roman dominating function on G. Note that the 1-distance Roman domination number γ_R^1 (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, γ_R^k (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.
Keywords: k-distance Roman dominating function, k-distance Roman domination number, Roman dominating function, Roman domination number 
@article{DMGT_2013_33_4_a7,
     author = {Aram, Hamideh and Norouzian, Sepideh and Sheikholeslami, Seyed Mahmoud},
     title = {The {Distance} {Roman} {Domination} {Numbers} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {717--730},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a7/}
}
TY  - JOUR
AU  - Aram, Hamideh
AU  - Norouzian, Sepideh
AU  - Sheikholeslami, Seyed Mahmoud
TI  - The Distance Roman Domination Numbers of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 717
EP  - 730
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a7/
LA  - en
ID  - DMGT_2013_33_4_a7
ER  - 
%0 Journal Article
%A Aram, Hamideh
%A Norouzian, Sepideh
%A Sheikholeslami, Seyed Mahmoud
%T The Distance Roman Domination Numbers of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 717-730
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a7/
%G en
%F DMGT_2013_33_4_a7
Aram, Hamideh; Norouzian, Sepideh; Sheikholeslami, Seyed Mahmoud. The Distance Roman Domination Numbers of Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 717-730. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a7/

[1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications (The Macmillan Press Ltd. London and Basingstoke, 1976).

[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

[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

[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.

[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

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. NewYork, 1998).

[7] B.P. Mobaraky and S.M. Sheikholeslami, Bounds on Roman domination numbers of a graph, Mat. Vesnik 60 (2008) 247-253.

[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

[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).