On the double Roman domination of graphs

Jun Yue, Meiqin Wei, Min Li and Guodong Liu

Applied Mathematics and Computation, 2018, vol. 338, issue C, 669-675

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

Keywords: Double Roman domination; Double Roman domination number; Nordhaus–Gaddum type problem; Cograph; Algorithm (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318305228
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:338:y:2018:i:c:p:669-675

DOI: 10.1016/j.amc.2018.06.033

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().