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.