Shahed University
Some progress on the double Roman domination in graphs
Nader Jafari Rad | Hadi Rahbani
URL :
http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=85636
Date :
2018/11/09
Publish in :
Discussiones Mathematicae Graph Theory
DOI :
https://doi.org/10.7151/dmgt.2069
Link :
https://doi.org/10.7151/dmgt.2069
Keywords :
SOME, ROMAN, DOMINATION,DOUBL ROMAN
Abstract :
For a graph G = (V,E), a double Roman dominating function (or just DRDF) is a function f : V −→ 0, 1, 2, 3 having the property that if f(v) = 0 for a vertex v, then v has at least two neighbors assigned 2 under f or one neighbor assigned 3 under f, and if f(v) = 1, then vertex v must have at least one neighbor w with f(w) ≥ 2. The weight of a DRDF f is the sum f(V ) = Pv2V f(v), and the minimum weight of a DRDF on G is the double Roman domination number of G, denoted by dR(G). In this paper, we derive sharp upper and lower bounds on dR(G) + dR(G) and also dR(G) dR(G), where G is the complement of graph G. We also show that the decision problem for the double Roman domination number is NP- complete even when restricted to bipartite graphs and chordal graphs.
Files in this item :
Download
Name :
85636_9514673416.pdf
Size :
161Kb
Format :
PDF
Authors' Home page
Nader Jafari Rad