Maximal double Roman domination in graphs

Abstract

A maximal double Roman dominating function (MDRDF) on a graph $G=(V,E)$ is a function $f:V(G)\to \{0,1,2,3\}$ such that \textrm{(i) }every vertex $v$ with $f(v)=0$ is adjacent to least two vertices { assigned $2$ or to at least one vertex assigned $3,$} \textrm{(ii) }every vertex $v$ with $f(v)=1$ is adjacent to at least one { vertex assigned $2$ or $3$} and \textrm{(iii) }the set $\{w\in V|f(w)=0\}$ is not a dominating set of $G$. The weight of a MDRDF is the sum of its function values over all vertices, and the maximal double Roman domination number ${\gamma }_{dR}^m(G)$ is the minimum weight of an MDRDF on $G$. {In this paper, we initiate the study of maximal double Roman domination. We first show that the problem of determining }${\gamma }_{dR}^m(G)$ {is NP-complete for bipartite, chordal and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs and distance-hereditary graphs. Moreover, we establish various relationships relating }${\gamma }_{dR}^m(G)$ to some domination parameters. {For the class of trees, we show that for every tree }$T$ {of order }$n\ge 4,$ ${\gamma }_{dR}^m(T)\le \frac{5}{4}n$ {and we characterize all trees attaining the bound. Finally, the exact values of }${\gamma }_{dR}^m(G)$ {are given for paths and cycles.

References in corpus (2)

• Triple Roman Domination in Graphs
• Total Roman {2}-Dominating functions in Graphs

Cited by in corpus (2)

• A new approach on locally checkable problems
• On the outer independent total double Roman dominating functions