NUK - logo
E-viri
Celotno besedilo
Recenzirano
  • Maximal double Roman domina...
    Abdollahzadeh Ahangar, H.; Chellali, M.; Sheikholeslami, S.M.; Valenzuela-Tripodoro, J.C.

    Applied mathematics and computation, 02/2022, Letnik: 414
    Journal Article

    •We introduce maximal double Roman dominating functions in graphs and study the corresponding parameter γdRm(G).•We show that the problem of determining γdRm(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.•We establish various relationships relating γdRm(G) to some domination parameters.•For the class of trees, we show that for every tree T of order n≥4,γdRm(T)≤54n and we characterize all trees attaining the bound.•Finally, the exact values of γdRm(G) are given for paths and cycles. 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∈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 γdRm(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 γdRm(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 γdRm(G) to some domination parameters. For the class of trees, we show that for every tree T of order n≥4,γdRm(T)≤54n and we characterize all trees attaining the bound. Finally, the exact values of γdRm(G) are given for paths and cycles.