A maximal double Roman dominating function (MDRDF) on a graph G = (V, E) is a function f : V(G) -> {0, 1, 2, 3} such that (i) every vertex v with f (v) = 0 is adjacent to least two vertices assigned 2 or to at least one vertex assigned 3, (ii) every vertex v with f (v) = 1 is adjacent to at least one vertex assigned 2 or 3 and (iii) the set {w subset of V vertical bar 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(m)(dR)(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(m)(dR)(G) is NP-complete for bipartite, chordal and planar graphs. But it is solvable in linear time for bounded cliquewidth graphs including trees, cographs and distance-hereditary graphs. Moreover, we establish various relationships relating gamma(m)(dR)(G) to some domination parameters. For the class of trees, we show that for every tree T of order n >= 4, gamma(m)(dR)(T) <= 5/4n and we characterize all trees attaining the bound. Finally, the exact values of gamma(m)(dR)(G) are given for paths and cycles. (C) 2021 Elsevier Inc. All rights reserved.
Maximal double Roman dominationDouble Roman dominationMaximal Roman domination
Chellali, M.、Sheikholeslami, S. M.、Valenzuela-Tripodoro, J. C.、Ahangar, H. Abdollahzadeh
NSTL
Elsevier
