Authors: H.A. Ahangar, J. Amjadi, M. Chellali, S. Nazari-Moghaddam, S.M. Sheikholeslami Title: Total Roman reinforcement in graphs Source: Discussiones Mathematicae Graph Theory Received 19.06.2017, Revised 21.11.2017, Accepted 21.11.2017, doi: 10.7151/dmgt.2108 | |
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 dominating 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 properties 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 | |
Keywords: total Roman domination number, total Roman reinforcement number | |
Links: |