Er Fang SHAN, Moo Young SOHN, Xu Dong YUAN, Michael A.HENNING
A set D of vertices of a graph G=(V,E)is called a dominating set if every vertex of Vnot in D is adjacent to a vertex of D.In 1996,Reed proved that every graph of order n with minimumdegree at least 3 has a dominating set of cardinality at most 3n/8.In this paper we generalize Reed'sresult.We show that every graph G of order n with minimum degree at least 2 has a dominating set ofcardinality at most(3n+|V2|)/8,where V2 denotes the set of vertices of degree 2 in G.As an applicationof the above result,we show that for k≥1,the k-restricted domination number rk(G,γ)≤(3n+5k)/8for all graphs of order n with minimum degree at least 3.