Maximal double Roman domination in graphs
Identificadores
URI: http://hdl.handle.net/10498/30718
DOI: https://doi.org/10.1016/j.amc.2021.126662
ISSN: 0096-3003
Statistics
Metrics and citations
Metadata
Show full item recordDate
2022-02-01Department
MatemáticasSource
Applied Mathematics and Computation, 2022, Vol. 414Abstract
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 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 the maximal double Roman domination number 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 this parameter to some other domination parameters. For the class of trees, we show that for every tree T of order n≥4, 5/4 n is an upper bound for the maximal double Roman domination number and we characterize all trees attaining the bound. Finally, the exact value of this new domination parameter is given for paths and cycles.
Subjects
Roman domination; Double Roman domination; Maximal double dominationCollections
- Artículos Científicos [12023]






