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 rtR(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 rtR(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:
PDF