On upper bounds for multiple domination numbers of graphs

Consider a simple and finite graph G. A subset D of its vertex set V is a dominating set if vertical bar(N(v) U {v}) boolean AND D vertical bar >= 1 for each V is an element of V. Several "multiple" counterparts of such sets are known. In particular, D is said to be a k-dominating set, if every vertex v not in D satisfies vertical bar N(v) boolean AND D vertical bar >= k, or a k-tuple dominating set if vertical bar(N(v) boolean OR {v}) boolean AND D vertical bar >= k for each v is an element of V, or a k-tuple total dominating set if every vertex has at least k neighbours in D. We generalize a well known result by Alon and Spencer concerning dominating sets to obtain new upper bounds for the minimum size of their multiple analogues. These also provide upper bounds in a generalized concept of so-called liar's dominating sets, which were first introduced by Slater. (C) 2013 Elsevier B.V. All rights reserved.