SHAN Er-fang, Moo Young Sohn
Acta Mathematica Sinica. 2009, 25(8): 0-0.
A set D of vertices of a graph G=(V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. The domination number of G, denoted by
$\gamma (G)$, is the size of its smallest dominating set. The k-restricted domination number of a graph G, denoted by $r_k(G, \gamma)$, is the smallest integer $d_k$ such that given any subset $U$ of $k$ vertices of $G$, there exists a dominating set of
G of cardinality at most $d_k$ containing $U$. When $k=0$, the k-restricted domination number is the domination number. Reed proved that every graph of order $n$ with minimum degree at least three has a dominating set of at most 3n/8 vertices. By modifying his method, we prove that every graph $G$ of order n
with minimum degree at least two has a dominating set of cardinality at most (3n+|V_2|)/8, where $V_2$ denotes the set of vertices of degree two in $G$. As an application of the above result, we show that for $k\ge 1$, $r_k(G, \gamma)\le (3n+5k)/8$ for all graphs of order $n$ and minimum degree at least three.
