| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419966 | Discrete Applied Mathematics | 2013 | 6 Pages |
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.
