On the restrained domination stability in graphs

A subset S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. A dominating set S is a restrained dominating set if for each vertex x is an element of V (G) - S there is a vertex y is an element of V (G) - S such that xy is an element of E(G). The restrained domination number of G, denoted by gamma r(G) is the minimum cardinality of a restrained dominating set of G. The restrained domination stability number of G, denoted by st gamma r (G), is the minimum number of vertices whose removal changes the restrained domination number of G. In this paper we study the restrained domination stability number of a graph and determine it for several families of graphs. We present bounds for the restrained domination stability number of a graph. We also prove that determining the restrained domination stability number is NP-hard even when restricted to bipartite graphs.