Connected odd dominating sets in graphs

Yair Caro; William F. Klostermeyer; Raphael Yuster

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 3, page 225-239
  • ISSN: 2083-5892

Abstract

top
An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.

How to cite

top

Yair Caro, William F. Klostermeyer, and Raphael Yuster. "Connected odd dominating sets in graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 225-239. <http://eudml.org/doc/270479>.

@article{YairCaro2005,
abstract = {An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.},
author = {Yair Caro, William F. Klostermeyer, Raphael Yuster},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {dominating set; odd dominating set},
language = {eng},
number = {3},
pages = {225-239},
title = {Connected odd dominating sets in graphs},
url = {http://eudml.org/doc/270479},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Yair Caro
AU - William F. Klostermeyer
AU - Raphael Yuster
TI - Connected odd dominating sets in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 3
SP - 225
EP - 239
AB - An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.
LA - eng
KW - dominating set; odd dominating set
UR - http://eudml.org/doc/270479
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. Combin. Math. and Combin. Comput. 20 (1996) 53-63. Zbl0845.05029
  4. [4] Y. Caro, Simple proofs to three parity theorems, Ars Combin. 42 (1996) 175-180. 
  5. [5] Y. Caro and W. Klostermeyer, The odd domination number of a graph, J. Combin. Math. Combin. Comput. 44 (2003) 65-84. Zbl1020.05047
  6. [6] Y. Caro, W. Klostermeyer and J. Goldwasser, Odd and residue domination numbers of a graph, Discuss. Math. Graph Theory 21 (2001) 119-136, doi: 10.7151/dmgt.1137. Zbl0991.05080
  7. [7] M. Conlon, M. Falidas, M. Forde, J. Kennedy, S. McIlwaine and J. Stern, Inversion numbers of graphs, Graph Theory Notes of New York XXXVII (1999) 43-49. 
  8. [8] R. Cowen, S. Hechler, J. Kennedy and A. Ryba, Inversion and neighborhood inversion in graphs, Graph Theory Notes of New York XXXVII (1999) 38-42. 
  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 18 (2002) 271-283, doi: 10.1007/s003730200020. 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) 101-109. 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] K. Sutner, Linear cellular automata and the Garden-of-Eden, The Mathematical Intelligencer 11 (2) (1989) 49-53, doi: 10.1007/BF03023823. 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.