## Abstract

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. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed's result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n+{pipe}V_{2}{pipe})/8, where V_{2} denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number r_{k}(G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3.

Original language | English |
---|---|

Pages (from-to) | 1253-1268 |

Number of pages | 16 |

Journal | Acta Mathematica Sinica, English Series |

Volume | 25 |

Issue number | 8 |

DOIs | |

Publication status | Published - Aug 2009 |

Externally published | Yes |

## Keywords

- Dominating set
- Domination number
- Graph
- Restricted domination number

## ASJC Scopus subject areas

- General Mathematics
- Applied Mathematics