Maximal double Roman domination in graphs

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Maximal double Roman domination,Double Roman domination,Maximal Roman domination

论文评审过程：Received 31 March 2021, Revised 26 July 2021, Accepted 15 September 2021, Available online 1 October 2021, Version of Record 1 October 2021.

论文官网地址：https://doi.org/10.1016/j.amc.2021.126662