On the double Roman domination of graphs

摘要

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