See supplemental content for abstract

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.

For a graph G with vertex set V(G) and function f:V(G)→{0,1,2,3}, let Vi be the set of vertices assigned i by f. A perfect double Roman dominating function of a graph G is a function f:V(G)→{0,1,2,3} satisfying the conditions that (i) if u∈V0, then u is either adjacent to exactly two vertices in V2 and no vertex in V3 or adjacent to exactly one vertex in V3 and no vertex in V2; and (ii) if u∈V1, then u is adjacent to exactly one vertex in V2 and no vertex in V3. The perfect double Roman domination number of G, denoted γdRp(G), is the minimum weight of a perfect double Roman dominating function of G. We prove that if T is a tree of order n≥3, then γdRp(T)≤9n∕7. In addition, we give a family of trees T of order n for which γdRp(T) approaches this upper bound as n goes to infinity.

No description available.

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination numberγt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑u ∈ V (G) f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only ifγt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.

In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E), a Roman {2}-dominating function f:V→{0,1,2} has the property that for every vertex v∈V with f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to least two vertices assigned 1 under f. The weight of a Roman {2}-dominating function is the sum Σv∈Vf(v), and the minimum weight of a Roman {2}-dominating function f is the Roman {2}-domination number. First, we present bounds relating the Roman {2}-domination number to some other domination parameters. In particular, we show that the Roman {2}-domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman {2}-domination is NP-complete, even for bipartite graphs.

We mainly study two related dominating functions, namely, the weak Roman and 2-rainbow dominating functions. We show that for all graphs, the weak Roman domination number is bounded above by the 2-rainbow domination number. We present bounds on the weak Roman domination number and the secure domination number in terms of the total domination number for specific families of graphs, and we show that the 2-rainbow domination number is bounded below by the total domination number for trees and for a subfamily of cactus graphs.

Let G= (V, E) be a simple graph with vertex set V and edge set E. A mixed Roman dominating function (MRDF) of G is a function f: V∪ E→ { 0 , 1 , 2 } satisfying the condition every element x∈ V∪ E for which f(x) = 0 is adjacent or incident to at least one element y∈ V∪ E for which f(y) = 2. The weight of a MRDF f is ω(f) = ∑ x∈V∪Ef(x). The mixed Roman domination number of G is the minimum weight of a mixed Roman dominating function of G. In this paper, we initiate the study of the mixed Roman domination number and we present bounds for this parameter. We characterize the graphs attaining an upper bound and the graphs having small mixed Roman domination numbers.

A Roman dominating function (RDF) on a graph G is a function f : V (G) → (0, 1,2) satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2. The weight of a Roman dominating function is the sum f(V ) = Σv∈Vf(v), and the minimum weight of a Roman dominating function f is the Roman domination number γR(G). An RDF f is called an independent Roman dominating function (IRDF) if the set of vertices assigned positive values under f is independent. The independent Roman domination number iR(G) is the minimum weight of an IRDF on G. We show that for every nontrivial connected graph G with maximum and i(G) are, respectively, the domination and independent domination numbers of G. Moreover, we characterize the connected graphs attaining each lower bound. We give an additional lower bound for γR(G) and compare our two new bounds on γR(G) with some known lower bounds.

For a graph (Formula presented.), a Roman dominating function (Formula presented.) has the property that every vertex (Formula presented.) with (Formula presented.) has a neighbor (Formula presented.) with (Formula presented.). The weight of a Roman dominating function (Formula presented.) is the sum (Formula presented.), and the minimum weight of a Roman dominating function on (Formula presented.) is the Roman domination number of (Formula presented.). In this paper, we define the Roman independence number, the upper Roman domination number and the upper and lower Roman irredundance numbers, and then develop a Roman domination chain parallel to the well-known domination chain. We also develop sharpness, strictness and bounds for the Roman domination chain inequalities.