# On non-z(mod k) dominating sets

Yair Caro; Michael S. Jacobson

Discussiones Mathematicae Graph Theory (2003)

- Volume: 23, Issue: 1, page 189-199
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYair 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 -

## References

top- [1] A. Amin and P. Slater, Neighborhood Domination with Parity Restriction in Graphs, Congr. Numer. 91 (1992) 19-30. Zbl0798.68135
- [2] A. Amin and P. Slater, All Parity Realizable Trees, J. Combin. Math. Combin. Comput. 20 (1996) 53-63. Zbl0845.05029
- [3] Y. Caro, Simple Proofs to Three Parity Theorems, Ars Combin. 42 (1996) 175-180. Zbl0852.05067
- [4] Y. Caro and W.F. Klostermeyer, The odd domination number of a graph, to appear in J. Combin. Math. Combin. Comput. Zbl1020.05047
- [5] Y. Caro, J. Goldwasser and W. Klostermeyer, Odd and Residue Domination Numbers of a Graph, Discuss. Math. Graph Theory 21 (2001) 119-136, doi: 10.7151/dmgt.1137. Zbl0991.05080
- [6] J. Goldwasser and W. Klostermeyer, Maximization Versions of Lights Out Games in Grids and Graphs, Congr. Numer. 126 (1997) 99-111. Zbl0897.05048
- [7] K. Sutner, Linear Cellular Automata and the Garden-of-Eden, Mathematical Intelligencer 11 (2) (1989) 49-53. Zbl0770.68094