Restrained domination in unicyclic graphs
Johannes H. Hattingh, Ernst J. Joubert, Marc A. Loizeaux, Andrew R Plummer, Lucas C. van der Merwe · Discussiones Mathematicae Graph Theory · 2009
Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V − S is adjacent to a vertex in S and to a vertex in V − S. The restrained domination number of G, denoted by γr(G), is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then γr(U) ≥ dn3 e, and provide a characterization of graphs achieving this bound.