Signed double Italian domination

Abstract

A signed double Italian dominating function (SDIDF) on a graph $ G = (V, E) $ is a function $ f $ from $ V $ to $ \{-1, 1, 2, 3\} $, satisfying (ⅰ) $ \sum_{u\in N[v]}f(u)\ge1 $ for all $ v\in V $; (ⅱ) if $ f(v) = -1 $ for some $ v\in V $, then there exists $ A\subseteq N(v) $ such that $ \sum_{u\in A}f(u)\ge3 $; and (ⅲ) if $ f(v) = 1 $ for some $ v\in V $, then there exists $ A\subseteq N(v) $ such that $ \sum_{u\in A}f(u)\ge2 $. The weight of an SDIDF $ f $ is $ \sum_{v\in V}f(v) $. The signed double Italian domination number of $ G $ is the minimum weight of an SDIDF on $ G $. In this paper, we initiated the study of signed double Italian domination and proved that the decision problem associated with the signed double Italian domination is NP-complete. We also provided tight lower and upper bounds of a signed double Italian domination number of trees, and we characterized the trees achieving these bounds. Finally, we determined the signed double Italian domination number for some well-known graphs.

Keywords

• signed double roman domination
• roman domination
• graph domination
• trees
• petersen graph