1. Domination number in graphs with minimum degree two.
- Author
-
Er Fang Shan, Moo Young Sohn, Xu Dong Yuan, and Henning, Michael A.
- Subjects
- *
GRAPH theory , *COMBINATORICS , *ALGEBRA , *TOPOLOGY , *GRAPHIC methods - 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 3 n/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 (3 n+| V2|)/8, where V2 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, γ) ≤ (3 n+5 k)/8 for all graphs of order n with minimum degree at least 3. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF