An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree
Let G=(V,E) G = ( V , E ) be a graph. A set S?V S ? V is a restrained dominating set if every vertex in V?S V ? S is adjacent to a vertex in S S and to a vertex in V?S V ? S . The restrained domination number of G G , denoted ?r(G) ? r ( G ) , is the smallest cardinality of a restrained dominating set of G G . We will show that if G G is a connected graph of order n n and minimum degree ? ? and not isomorphic to one of nine exceptional graphs, then ? r ( G ) ? n ? ? + 1 2 .
upper bound restrained domination domination graph minimum degree order of a graph