On non-z(mod k) dominating sets

Yair Caro, and Michael S. Jacobson. "On non-z(mod k) dominating sets." Discussiones Mathematicae Graph Theory 23.1 (2003): 189-199. <http://eudml.org/doc/270294>.

@article{YairCaro2003,
abstract = {For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 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| ≢ 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 ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 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.},
author = {Yair Caro, Michael S. Jacobson},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; tree; unicyclic graph},
language = {eng},
number = {1},
pages = {189-199},
title = {On non-z(mod k) dominating sets},
url = {http://eudml.org/doc/270294},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Yair Caro
AU - Michael S. Jacobson
TI - On non-z(mod k) dominating sets
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 189
EP - 199
AB - For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 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| ≢ 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 ≠ 1, that a non-z(mod k) dominating set exist for all trees. Also, it will be shown that for k ≥ 4, z ≥ 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.
LA - eng
KW - dominating set; tree; unicyclic graph
UR - http://eudml.org/doc/270294
ER -