Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8900666 | Applied Mathematics and Computation | 2018 | 7 Pages |
Abstract
A double Roman dominating function of a graph G is a labeling f: V(G)â¯ââ¯{0, 1, 2, 3} such that if f(v)=0, then the vertex v must have at least two neighbors labeled 2 under f or one neighbor with f(w)=3, and if f(v)=1, then v must have at least one neighbor with f(w)â¯â¥â¯2. The double Roman domination number γdR(G) of G is the minimum value of Σvâ¯ââ¯V(G)f(v) over such functions. In this paper, we firstly give some bounds of the double Roman domination numbers of graphs with given minimum degree and graphs of diameter 2, and further we get that the double Roman domination numbers of almost all graphs are at most n. Then we obtain sharp upper and lower bounds for γdR(G)+γdR(G¯). Moreover, a linear time algorithm for the double Roman domination number of a cograph is given and a characterization of the double Roman cographs is provided. Those results partially answer two open problems posed by Beeler et al. (2016).
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Jun Yue, Meiqin Wei, Min Li, Guodong Liu,