Quasi total double Roman domination in graphs

Abstract

A quasi total double Roman dominating function (QTDRD-function) on a graph [Formula: see text] is a function [Formula: see text] having the property that (i) if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3; (ii) if f(v) = 1, then vertex v has at least one neighbor w with [Formula: see text], and (iii) if x is an isolated vertex in the subgraph induced by the set of vertices assigned nonzero values, then f(x) = 2. The weight of a QTDRD-function f is the sum of its function values over the whole vertices, and the quasi total double Roman domination number [Formula: see text] equals the minimum weight of a QTDRD-function on G. In this paper, we first show that the problem of computing the quasi total double Roman domination number of a graph is NP-hard, and then we characterize graphs G with small or large [Formula: see text]. Moreover, we establish an upper bound on the quasi total double Roman domination number and we characterize the connected graphs attaining this bound.

Keywords

• Quasi total double Roman domination
• total double Roman domination
• double Roman domination number
• Roman domination number
• 05C69