# 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

## Access Full Article

top## Abstract

top## How to cite

topYair 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] 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] A. Amin and P. Slater, Neighborhood domination with parity restriction in graphs, Congr. Numer. 91 (1992) 19-30. Zbl0798.68135
- [3] A. Amin and P. Slater, All parity realizable trees, J. Combin. Math. and Combin. Comput. 20 (1996) 53-63. Zbl0845.05029
- [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. Combin. Math. Combin. Comput. 44 (2003) 65-84. Zbl1020.05047
- [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] 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] 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] 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] J. Goldwasser and W. Klostermeyer, Maximization versions of 'Lights Out' games in grids and graphs, Congr. Numer. 126 (1997) 99-111. Zbl0897.05048
- [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] 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] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [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 ?

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