Double Roman Domination
Document Type
Article
Publication Date
10-1-2016
Description
For a graph G=(V,E), a double Roman dominating function is a function f:V→{0,1,2,3} having the property that if f(v)=0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor with f(w)=3, and if f(v)=1, then vertex v must have at least one neighbor with f(w)≥2. The weight of a double Roman dominating function f is the sum f(V)=∑v∈Vf(v), and the minimum weight of a double Roman dominating function on G is the double Roman domination number of G. We initiate the study of double Roman domination and show its relationship to both domination and Roman domination. Finally, we present an upper bound on the double Roman domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound.
Citation Information
Beeler, Robert A.; Haynes, Teresa W.; and Hedetniemi, Stephen T.. 2016. Double Roman Domination. Discrete Applied Mathematics. Vol.211 23-29. https://doi.org/10.1016/j.dam.2016.03.017 ISSN: 0166-218X