Geodesic
Odd and residue domination numbers of a graph
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 1, pp. 119-136.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: dominating set, odd dominating set, parity domination 
@article{DMGT_2001_21_1_a8,
     author = {Caro, Yair and Klostermeyer, William and Goldwasser, John},
     title = {Odd and residue domination numbers of a graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {119--136},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a8/}
}
TY  - JOUR
AU  - Caro, Yair
AU  - Klostermeyer, William
AU  - Goldwasser, John
TI  - Odd and residue domination numbers of a graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 119
EP  - 136
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a8/
LA  - en
ID  - DMGT_2001_21_1_a8
ER  - 
%0 Journal Article
%A Caro, Yair
%A Klostermeyer, William
%A Goldwasser, John
%T Odd and residue domination numbers of a graph
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 119-136
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a8/
%G en
%F DMGT_2001_21_1_a8
Caro, Yair; Klostermeyer, William; Goldwasser, John. Odd and residue domination numbers of a graph. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 1, pp. 119-136. http://geodesic.mathdoc.fr/item/DMGT_2001_21_1_a8/

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

[2] A. Amin and P. Slater, Neighborhood Domination with Parity Restriction in Graphs, Congr. Numer. 91 (1992) 19-30.

[3] A. Amin and P. Slater, All Parity Realizable Trees, J. Comb. Math. Comb. Comput. 20 (1996) 53-63.

[4] Y. Caro, Simple Proofs to Three Parity Theorems, Ars Combin. 42 (1996) 175-180.

[5] Y. Caro and W. Klostermeyer, The Odd Domination Number of a Graph, J. Comb. Math. Comb. Comput. (2000), to appear.

[6] E. Cockayne, E. Hare, S. Hedetniemi and T. Wimer, Bounds for the Domination Number of Grid Graphs, Congr. Numer. 47 (1985) 217-228.

[7] M. Garey and D. Johnson, Computers and Intractability (W.H. Freeman, San Francisco, 1979).

[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).

[9] J. Goldwasser, W. Klostermeyer and G. Trapp, Characterizing Switch-Setting Problems, Linear and Multilinear Algebra 43 (1997) 121-135, doi: 10.1080/03081089708818520.

[10] J. Goldwasser and W. Klostermeyer, Maximization Versions of ``Lights Out'' Games in Grids and Graphs, Congr. Numer. 126 (1997) 99-111.

[11] J. Goldwasser, W. Klostermeyer and H. Ware, Fibonacci Polynomials and Parity Domination in Grid Graphs, Graphs and Combinatorics (2000), to appear.

[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).

[13] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[14] R. Johnson and C. Johnson, Matrix Analysis (Cambridge University Press, 1990).

[15] M. Jacobson and L. Kinch, On the Domination Number of Products of Graphs, Ars Combin. 18 (1984) 33-44.

[16] W. Klostermeyer and E. Eschen, Perfect Codes and Independent Dominating Sets, Congr. Numer. (2000), to appear.

[17] K. Sutner, Linear Cellular Automata and the Garden-of-Eden, The Mathematical Intelligencer 11 (2) (1989) 49-53.