# The Distance Roman Domination Numbers of Graphs

• Volume: 33, Issue: 4, page 717-730
• ISSN: 2083-5892

top

## Abstract

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

## How to cite

top

Hamideh Aram, Sepideh Norouzian, and Seyed Mahmoud Sheikholeslami. "The Distance Roman Domination Numbers of Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 717-730. <http://eudml.org/doc/268287>.

@article{HamidehAram2013,
abstract = {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.},
author = {Hamideh Aram, Sepideh Norouzian, Seyed Mahmoud Sheikholeslami},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-distance Roman dominating function; k-distance Roman domination number; Roman dominating function; Roman domination number; -distance Roman dominating function; -distance Roman domination number},
language = {eng},
number = {4},
pages = {717-730},
title = {The Distance Roman Domination Numbers of Graphs},
url = {http://eudml.org/doc/268287},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Hamideh Aram
AU - Sepideh Norouzian
AU - Seyed Mahmoud Sheikholeslami
TI - The Distance Roman Domination Numbers of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 4
SP - 717
EP - 730
AB - 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.
LA - eng
KW - k-distance Roman dominating function; k-distance Roman domination number; Roman dominating function; Roman domination number; -distance Roman dominating function; -distance Roman domination number
UR - http://eudml.org/doc/268287
ER -

## References

top
1. [1] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications (The Macmillan Press Ltd. London and Basingstoke, 1976). Zbl1226.05083
2. [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] Zbl1207.05135
3. [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] Zbl1036.05034
4. [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. Zbl1081.05083
5. [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] Zbl1191.05071
6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. NewYork, 1998). Zbl0890.05002
7. [7] B.P. Mobaraky and S.M. Sheikholeslami, Bounds on Roman domination numbers of a graph, Mat. Vesnik 60 (2008) 247-253. Zbl1274.05359
8. [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] Zbl1039.90038
9. [9] I. Stewart, Defend the Roman Empire, Sci. Amer. 281 (1999) 136-139.
10. [10] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000).

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.