On the total Roman domination stability in graphs

Abstract

A total Roman dominating function on a graph G is a function satisfying the conditions: (i) every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2; (ii) the subgraph induced by the vertices assigned non-zero values has no isolated vertices. The minimum of over all such functions is called the total Roman domination number The total Roman domination stability number of a graph G with no isolated vertex, denoted by is the minimum number of vertices whose removal does not produce isolated vertices and changes the total Roman domination number of G. In this paper we present some bounds for the total Roman domination stability number of a graph, and prove that the associated decision problem is NP-hard even when restricted to bipartite graphs or planar graphs.

Keywords

• roman domination
• total roman domination
• complexity