مشخصات پژوهش

An outer-independent triple Roman dominating function (OI[3]RDF) on a graph G = (V,E) is a function f : V →{0,1,2,3,4} having the property that (i) if f(v)=0, then v must have either a neighbor assigned 4 or two neighbors one of which is assigned 3 and the other at least 2 or v has three neighbors all assigned 2; (ii) no two vertices assigned 0 are adjacent; (iii) if f(v)=1,thenv must have either a neighbor assigned at least 3 or two neighbors assigned 2; (iv) if f(v)=2,thenv 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 G is the minimum weight of an OI[3]RDF on G. 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.