Algorithmic aspects of total Roman {3}-domination in graphs

Source abstract

For a simple, undirected, connected graph [Formula: see text], a function [Formula: see text] which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of [Formula: see text] with weight [Formula: see text]: (C1) For every vertex [Formula: see text] if [Formula: see text], then [Formula: see text] has [Formula: see text] ([Formula: see text]) neighbors such that whose sum is at least 3, and if [Formula: see text], then [Formula: see text] has [Formula: see text] ([Formula: see text]) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph [Formula: see text], the smallest possible weight of a TR3DF of [Formula: see text] denoted [Formula: see text] is known as the total Roman[Formula: see text]-domination number of [Formula: see text]. The problem of determining [Formula: see text] of a graph [Formula: see text] is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if [Formula: see text] has a TR3DF of weight at most [Formula: see text] for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a [Formula: see text]-approximation algorithm for the MTR3DP and show that the same cannot have [Formula: see text] ratio approximation algorithm for any [Formula: see text] unless NP [Formula: see text]. Next, we show that MTR3DP is APX-complete for graphs with [Formula: see text]. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP.