Odd and residue domination numbers of a graph

Yair Caro; William F. Klostermeyer; John L. Goldwasser

Discussiones Mathematicae Graph Theory (2001)

  • Volume: 21, Issue: 1, page 119-136
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Yair Caro, William F. Klostermeyer, and John L. Goldwasser. "Odd and residue domination numbers of a graph." Discussiones Mathematicae Graph Theory 21.1 (2001): 119-136. <http://eudml.org/doc/270762>.

@article{YairCaro2001,
abstract = {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.},
author = {Yair Caro, William F. Klostermeyer, John L. Goldwasser},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; odd dominating set; parity domination},
language = {eng},
number = {1},
pages = {119-136},
title = {Odd and residue domination numbers of a graph},
url = {http://eudml.org/doc/270762},
volume = {21},
year = {2001},
}

TY - JOUR
AU - Yair Caro
AU - William F. Klostermeyer
AU - John L. Goldwasser
TI - Odd and residue domination numbers of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2001
VL - 21
IS - 1
SP - 119
EP - 136
AB - 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.
LA - eng
KW - dominating set; odd dominating set; parity domination
UR - http://eudml.org/doc/270762
ER -

References

top
  1. [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. Zbl0957.05058
  2. [2] A. Amin and P. Slater, Neighborhood Domination with Parity Restriction in Graphs, Congr. Numer. 91 (1992) 19-30. Zbl0798.68135
  3. [3] A. Amin and P. Slater, All Parity Realizable Trees, J. Comb. Math. Comb. Comput. 20 (1996) 53-63. Zbl0845.05029
  4. [4] Y. Caro, Simple Proofs to Three Parity Theorems, Ars Combin. 42 (1996) 175-180. Zbl0852.05067
  5. [5] Y. Caro and W. Klostermeyer, The Odd Domination Number of a Graph, J. Comb. Math. Comb. Comput. (2000), to appear. Zbl1020.05047
  6. [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. [7] M. Garey and D. Johnson, Computers and Intractability (W.H. Freeman, San Francisco, 1979). 
  8. [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. [9] J. Goldwasser, W. Klostermeyer and G. Trapp, Characterizing Switch-Setting Problems, Linear and Multilinear Algebra 43 (1997) 121-135, doi: 10.1080/03081089708818520. Zbl0890.15004
  10. [10] J. Goldwasser and W. Klostermeyer, Maximization Versions of ``Lights Out'' Games in Grids and Graphs, Congr. Numer. 126 (1997) 99-111. Zbl0897.05048
  11. [11] J. Goldwasser, W. Klostermeyer and H. Ware, Fibonacci Polynomials and Parity Domination in Grid Graphs, Graphs and Combinatorics (2000), to appear. Zbl0999.05079
  12. [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). Zbl0943.05081
  13. [13] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  14. [14] R. Johnson and C. Johnson, Matrix Analysis (Cambridge University Press, 1990). Zbl0704.15002
  15. [15] M. Jacobson and L. Kinch, On the Domination Number of Products of Graphs, Ars Combin. 18 (1984) 33-44. Zbl0566.05050
  16. [16] W. Klostermeyer and E. Eschen, Perfect Codes and Independent Dominating Sets, Congr. Numer. (2000), to appear. Zbl0976.05044
  17. [17] K. Sutner, Linear Cellular Automata and the Garden-of-Eden, The 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.