Outer-independent triple Roman domination

An outer-independent triple Roman dominating function (OI[3]RDF) on a graph [Formula: see text] is a function [Formula: see text] having the property that (i) if [Formula: see text] then [Formula: see text] must have either a neighbor assigned [Formula: see text] or two neighbors one of which is assigned 3 and the other at least 2 or [Formula: see text] has three neighbors all assigned 2; (ii) no two vertices assigned 0 are adjacent; (iii) if [Formula: see text], then [Formula: see text] must have either a neighbor assigned at least 3 or two neighbors assigned 2; (iv) if [Formula: see text], then [Formula: see text] must have one neighbor assigned at least 2. The weight of an OI[3]RDF is the sum of its function value over the whole set of vertices, and the outer-independent triple Roman domination number of [Formula: see text] is the minimum weight of an OI[3]RDF on [Formula: see text] In this paper, we begin the study of the outer-independent triple Roman domination number by presenting some bounds on it as well as exact values for some classes of graphs. For the class of trees, an upper bound is established in terms of the order and extremal trees reaching this bound are characterized. We also show that the decision problem associated with the outer-independent triple Roman domination problem is NP-complete for bipartite and chordal graphs.