Parity of an odd dominating set

Abstract

For a simple graph $G$ with vertex set $V(G)=\{v_1,...,v_n\}$, we define the closed neighborhood set of a vertex $u$ as \\$N[u]=\{v \in V(G) \; | \; v \; \text{is adjacent to} \; u \; \text{or} \; v=u \}$ and the closed neighborhood matrix $N(G)$ as the matrix whose $i$th column is the characteristic vector of $N[v_i]$. We say a set $S$ is odd dominating if $N[u]\cap S$ is odd for all $u\in V(G)$. We prove that the parity of the cardinality of an odd dominating set of $G$ is equal to the parity of the rank of $G$, where rank of $G$ is defined as the dimension of the column space of $N(G)$. Using this result we prove several corollaries in one of which we obtain a general formula for the nullity of the join of graphs.

Keywords

• Lights out
• all-ones problem
• odd dominating set
• parity domination
• domination number

References

1. Amin, A. T., Slater, P. J., Neighborhood domination with parity restrictions in graphs, In Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1992), 91 (1992), 19–30.
2. Amin, A. T., Slater, P. J., All parity realizable trees, J. Combin. Math. Combin. Comput., 20 (1996), 53–63.
3. Amin, A. T., Clark, L. H., Slater, P. J., Parity dimension for graphs, Discrete Math., 187(1-3) (1998), 1–17. https://doi.org/10.1016/S0012-365X(97)00242-2
4. Amin, A. T., Slater, P. J., Zhang, G. H., Parity dimension for graphs a linear algebraic approach, Linear Multilinear Algebra, 50(4) (2002), 327–342. https://doi.org/10.1080/0308108021000049293
5. Ballard, L. E., Budge, E. L., Stephenson, D. R., Lights out for graphs related to one another by constructions, Involve, 12(2) (2019), 181–201. https://doi.org/10.2140/involve.2019.12.181
6. Caro, Y., Simple proofs to three parity theorems, Ars Combin., 42 (1996), 175–180.
7. Cowen, R., Hechler, S. H., Kennedy, J. W., Ryba, A., Inversion and neighborhood inversion in graphs, Graph Theory Notes N. Y., 37 (1999), 37–41.
8. Eriksson, H., Eriksson, K., Sj¨ostrand, J., Note on the lamp lighting problem, Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000), 27 (2001), 357–366. https://doi.org/10.1006/aama.2001.0739

9. Sutner, K., Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11(2) (1989), 49–53. https://doi.org/10.1007/BF03023823
10. Sutner, K., The σ-game and cellular automata, Amer. Math. Monthly, 97(1) (1990), 24–34. https://doi.org/10.1080/00029890.1990.11995540