DOMINATION IN GRAPHS WITH MINIMUM DEGREE SIX

A set D of vertices of a graph G = (V(G),E(G)) is called a dominating set if every vertex of V(G) - D is adjacent to at least one element of D. The domination number of G, denoted by , is the size of its smallest dominating set. Haynes et al.[5] present a conjecture: For any graph G with ,. When , the conjecture was proved in [7], [8], [10], [12] and [13] respectively. In this paper we prove that every graph G on n vertices with has a dominating set of order at most . Thus the conjecture was completely proved.