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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16281 |
| Date | 01 October 2016 |
| Creators | Beeler, Robert A., Haynes, Teresa W., Hedetniemi, Stephen T. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.014 seconds