On the total Roman domination stability in graphs

Nader Jafari Rad | A. Tehranian | H. Rasooli | G. Asemian

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=169864
Date :  2021/10/09
Publish in :     AKCE International Journal of Graphs and Combinatorics

Link :  https://www.tandfonline.com/doi/full/10.1080/09728600.2021.1992257
Keywords : Roman dominationtotal Roman domination complexity

Abstract :

---

A total Roman dominating function on a graph G is a function f:V→0,1,2 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 f(V(G))=∑v∈Vf(v) over all such functions is called the total Roman domination number γtR(G). The total Roman domination stability number of a graph G with no isolated vertex, denoted by stγtR(G), 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.