|
Abstract
|
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.
|