Parity of an odd dominating set

Year 2022, , 1023 - 1028, 30.12.2022

Ahmet Batal

https://doi.org/10.31801/cfsuasmas.1051208

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

• 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.
• Amin, A. T., Slater, P. J., All parity realizable trees, J. Combin. Math. Combin. Comput., 20 (1996), 53–63.
• 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
• 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
• 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
• Caro, Y., Simple proofs to three parity theorems, Ars Combin., 42 (1996), 175–180.
• 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.
• 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
• Sutner, K., Linear cellular automata and the Garden-of-Eden, Math. Intelligencer, 11(2) (1989), 49–53. https://doi.org/10.1007/BF03023823
• Sutner, K., The σ-game and cellular automata, Amer. Math. Monthly, 97(1) (1990), 24–34. https://doi.org/10.1080/00029890.1990.11995540