On non-z(mod k) dominating sets
Yair Caro, Michael S. Jacobson · Discussiones Mathematicae Graph Theory · 2003
For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z 6= 1, a subset D of the vertex set V (G) is said to be a non-z(mod k) dominating set if D is a dominating set and for all x ∈ V (G), |N [x] ∩D| 6≡ z(mod k). For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with z < k and z 6= 1, that a non-z(mod k) dominating set exists for all trees. Also, it will be shown that for k ≥ 4, z 6= 1, 2 or 3 that any unicyclic graph contains a non-z(mod k) dominating set. We also give a few special cases of other families of graphs for which these dominating sets must exist.