Maximal double Roman domination in graphs

H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami and J.C. Valenzuela-Tripodoro

Applied Mathematics and Computation, 2022, vol. 414, issue C

Abstract: 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.

Keywords: Maximal double Roman domination; Double Roman domination; Maximal Roman domination (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300321007463
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:414:y:2022:i:c:s0096300321007463

DOI: 10.1016/j.amc.2021.126662

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().