|
Abstract
|
A total Roman dominating function on a graph G is a labeling f :
V (G) → {0,1,2} such that every vertex with label 0 has a neighbor with
label 2 and the subgraph of G induced by the set of all vertices of positive
weight has no isolated vertex. The minimum weight of a total Roman domi-
nating function on a graph G is called the total Roman domination number
of G. The total Roman reinforcement number r tR (G) of a graph G is the
minimum number of edges that must be added to G in order to decrease the
total Roman domination number. In this paper, we investigate the proper-
ties of total Roman reinforcement number in graphs, and we present some
sharp bounds for r tR (G). Moreover, we show that the decision problem for
total Roman reinforcement is NP-hard for bipartite graphs
|