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 ∈ V (G) − S there is a vertex y ∈ V (G) − S such that xy ∈ E(G). The restrained domination number of G, denoted by γr(G) is the minimum cardinality of a restrained dominating set of G. The restrained domination stability number of G, denoted by stγ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.