# On non-z(mod k) dominating sets

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

top

## Abstract

top
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.

## How to cite

top

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 -

## References

top
1. [1] A. Amin and P. Slater, Neighborhood Domination with Parity Restriction in Graphs, Congr. Numer. 91 (1992) 19-30. Zbl0798.68135
2. [2] A. Amin and P. Slater, All Parity Realizable Trees, J. Combin. Math. Combin. Comput. 20 (1996) 53-63. Zbl0845.05029
3. [3] Y. Caro, Simple Proofs to Three Parity Theorems, Ars Combin. 42 (1996) 175-180. Zbl0852.05067
4. [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. [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. [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. [7] K. Sutner, Linear Cellular Automata and the Garden-of-Eden, Mathematical Intelligencer 11 (2) (1989) 49-53. Zbl0770.68094

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.