On upper bounds for multiple domination numbers of graphs

Consider a simple and finite graph GG. A subset DD of its vertex set VV is a dominating set   if |(N(v)∪{v})∩D|≥1|(N(v)∪{v})∩D|≥1 for each v∈Vv∈V. Several “multiple” counterparts of such sets are known. In particular, DD is said to be a kk-dominating set  , if every vertex vv not in DD satisfies |N(v)∩D|≥k|N(v)∩D|≥k, or a kk-tuple dominating set   if |(N(v)∪{v})∩D|≥k|(N(v)∪{v})∩D|≥k for each v∈Vv∈V, or a kk-tuple total dominating set   if every vertex has at least kk neighbours in DD. 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.