We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
THE DISTANCE ROMAN DOMINATION NUMBERS OF GRAPHS.
- Authors
ARAM, HAMIDEH; NOROUZIAN, SEPIDEH; SHEIKHOLESLAMI, SEYED MAHMOUD; VOLKMANN, LUTZ
- 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 ω(f) = ∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γRk (D), equals the minimum weight of a k-distance Roman dominating function on G. Note that the 1-distance Roman domination number γRk (G) is the usual Roman domination number γR 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, γRk (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.
- Subjects
ROMAN numerals; GRAPH labelings; INTEGERS; MATHEMATICAL functions; PROOF theory; MATHEMATICAL bounds; GRAPH connectivity
- Publication
Discussiones Mathematicae: Graph Theory, 2013, Vol 33, Issue 4, p717
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.1703