Let G = (V,E) be a simple, undirected graph. A set of vertices D is called an odd dominating set if |N[v] ∩ D| ≡ 1 (mod 2) for every vertex v ∈ V(G). The minimum cardinality of an odd dominating set is called the odd domination number of G, denoted by γ₁(G). In this paper, several algorithmic and structural results are presented on this parameter for grids, complements of powers of cycles, and other graph classes as well as for more general forms of "residue" domination.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1137,
author = {Yair Caro and William F. Klostermeyer and John L. Goldwasser},
title = {Odd and residue domination numbers of a graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {21},
year = {2001},
pages = {119-136},
zbl = {0991.05080},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1137}
}
Yair Caro; William F. Klostermeyer; John L. Goldwasser. Odd and residue domination numbers of a graph. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 119-136. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1137/
[000] [1] A. Amin, L. Clark, and P. Slater, Parity Dimension for Graphs, Discrete Math. 187 (1998) 1-17, doi: 10.1016/S0012-365X(97)00242-2. | Zbl 0957.05058
[001] [2] A. Amin and P. Slater, Neighborhood Domination with Parity Restriction in Graphs, Congr. Numer. 91 (1992) 19-30. | Zbl 0798.68135
[002] [3] A. Amin and P. Slater, All Parity Realizable Trees, J. Comb. Math. Comb. Comput. 20 (1996) 53-63. | Zbl 0845.05029
[003] [4] Y. Caro, Simple Proofs to Three Parity Theorems, Ars Combin. 42 (1996) 175-180. | Zbl 0852.05067
[004] [5] Y. Caro and W. Klostermeyer, The Odd Domination Number of a Graph, J. Comb. Math. Comb. Comput. (2000), to appear. | Zbl 1020.05047
[005] [6] E. Cockayne, E. Hare, S. Hedetniemi and T. Wimer, Bounds for the Domination Number of Grid Graphs, Congr. Numer. 47 (1985) 217-228.
[006] [7] M. Garey and D. Johnson, Computers and Intractability (W.H. Freeman, San Francisco, 1979).
[007] [8] J. Goldwasser, W. Klostermeyer, G. Trapp and C.-Q. Zhang, Setting Switches on a Grid, Technical Report TR-95-20, Dept. of Statistics and Computer Science (West Virginia University, 1995).
[008] [9] J. Goldwasser, W. Klostermeyer and G. Trapp, Characterizing Switch-Setting Problems, Linear and Multilinear Algebra 43 (1997) 121-135, doi: 10.1080/03081089708818520. | Zbl 0890.15004
[009] [10] J. Goldwasser and W. Klostermeyer, Maximization Versions of ``Lights Out'' Games in Grids and Graphs, Congr. Numer. 126 (1997) 99-111. | Zbl 0897.05048
[010] [11] J. Goldwasser, W. Klostermeyer and H. Ware, Fibonacci Polynomials and Parity Domination in Grid Graphs, Graphs and Combinatorics (2000), to appear. | Zbl 0999.05079
[011] [12] M. Halldorsson, J. Kratochvil and J. Telle, Mod-2 Independence and Domination in Graphs, in: Proceedings Workshop on Graph-Theoretic Concepts in Computer Science '99, Ascona, Switzerland (Springer-Verlag, Lecture Notes in Computer Science, 1999). | Zbl 0943.05081
[012] [13] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[013] [14] R. Johnson and C. Johnson, Matrix Analysis (Cambridge University Press, 1990). | Zbl 0704.15002
[014] [15] M. Jacobson and L. Kinch, On the Domination Number of Products of Graphs, Ars Combin. 18 (1984) 33-44. | Zbl 0566.05050
[015] [16] W. Klostermeyer and E. Eschen, Perfect Codes and Independent Dominating Sets, Congr. Numer. (2000), to appear. | Zbl 0976.05044
[016] [17] K. Sutner, Linear Cellular Automata and the Garden-of-Eden, The Mathematical Intelligencer 11 (2) (1989) 49-53. | Zbl 0770.68094