Double Roman and double Italian domination

Volkmann, Lutz 

Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 721-730

Résumé

Let G be a graph with vertex set V(G). A double Roman dominating function (DRDF) on a graph G is a function f:V(G)⟶{0,1,2,3} that satisfies the following conditions: (i) If f(v)=0, then v must have a neighbor w with f(w)=3 or two neighbors x and y with f(x)=f(y)=2; (ii) If f(v)=1, then v must have a neighbor w with f(w)≥ 2. The weight of a DRDF f is the sum ∑_v∈ V(G)f(v). The double Roman domination number equals the minimum weight of a double Roman dominating function on G. A double Italian dominating function (DIDF) is a function f:V(G)⟶{0,1,2,3} having the property that f(N[u])≥ 3 for every vertex u∈ V(G) with f(u)∈{0,1}, where N[u] is the closed neighborhood of v. The weight of a DIDF f is the sum ∑_v∈ V(G)f(v), and the minimum weight of a DIDF in a graph G is the double Italian domination number. In this paper we first present Nordhaus-Gaddum type bounds on the double Roman domination number which improved corresponding results given in [N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019) 41–53]. Furthermore, we establish lower bounds on the double Roman and double Italian domination numbers of trees.

Détail

Keywords: double Roman domination, double Italian domination