Bounds on the 2-domination number

In a graph G, a set D subset of V(G) is called 2-dominating set if each vertex not in D has at least two neighbors in D. The 2-domination number gamma(2)(G) is the minimum cardinality of such a set D. We give a method for the construction of 2-dominating sets, which also yields upper bounds on the 2-domination number in terms of the number of vertices, if the minimum degree delta(G) is fixed. These improve the best earlier bounds for any 6 <= delta(G) <= 21. In particular, we prove that gamma(2)(G) is strictly smaller than n/2, if delta(G) >= 6. Our proof technique uses a weight-assignment to the vertices where the weights are changed during the procedure. (C) 2017 Elsevier B.V. All rights reserved.