Independent roman \{۳\}-domination

Let G be a simple, undirected graph. In this paper, we initiate the study of independent Roman \{۳\}-domination. A function g : V(G) \rightarrow \lbrace ۰, ۱, ۲, ۳ \rbrace having the property that \sum_{v \in N_G(u)}^{} g(v) \geq ۳, if g(u) = ۰, and \sum_{v \in N_G(u)}^{} g(v) \geq ۲, if g(u) = ۱ for any vertex u \in V(G), where N_G(u) is the set of vertices adjacent to u in G, and no two vertices assigned positive values are adjacent is called an \textit{ independent Roman \{۳\}-dominating function} (IR۳DF) of G. The weight of an IR۳DF g is the sum g(V) = \sum_{v \in V}g(v). Given a graph G and a positive integer k, the independent Roman \{۳\}-domination problem (IR۳DP) is to check whether G has an IR۳DF of weight at most k. We investigate the complexity of IR۳DP in bipartite and chordal graphs. The minimum independent Roman \lbrace ۳ \rbrace-domination problem (MIR۳DP) is to find an IR۳DF of minimum weight in the input graph. We show that MIR۳DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR۳DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR۳DP.

Keywords:

Roman ‎{۳}‎‎-domination , Independent Roman ‎{۳}‎‎-domination , NP-complete , APX-hard , Integer Linear Programming