Yıl: 2022 Cilt: 71 Sayı: 4 Sayfa Aralığı: 1023 - 1028 Metin Dili: İngilizce DOI: 10.31801/cfsuasmas.1051208 İndeks Tarihi: 30-12-2022

Parity of an odd dominating set

Öz:
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 $uin 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.
Anahtar Kelime: Lights out all-ones problem odd dominating set parity domination domination number

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • 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
APA Batal A (2022). Parity of an odd dominating set. , 1023 - 1028. 10.31801/cfsuasmas.1051208
Chicago Batal Ahmet Parity of an odd dominating set. (2022): 1023 - 1028. 10.31801/cfsuasmas.1051208
MLA Batal Ahmet Parity of an odd dominating set. , 2022, ss.1023 - 1028. 10.31801/cfsuasmas.1051208
AMA Batal A Parity of an odd dominating set. . 2022; 1023 - 1028. 10.31801/cfsuasmas.1051208
Vancouver Batal A Parity of an odd dominating set. . 2022; 1023 - 1028. 10.31801/cfsuasmas.1051208
IEEE Batal A "Parity of an odd dominating set." , ss.1023 - 1028, 2022. 10.31801/cfsuasmas.1051208
ISNAD Batal, Ahmet. "Parity of an odd dominating set". (2022), 1023-1028. https://doi.org/10.31801/cfsuasmas.1051208
APA Batal A (2022). Parity of an odd dominating set. Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics, 71(4), 1023 - 1028. 10.31801/cfsuasmas.1051208
Chicago Batal Ahmet Parity of an odd dominating set. Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics 71, no.4 (2022): 1023 - 1028. 10.31801/cfsuasmas.1051208
MLA Batal Ahmet Parity of an odd dominating set. Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics, vol.71, no.4, 2022, ss.1023 - 1028. 10.31801/cfsuasmas.1051208
AMA Batal A Parity of an odd dominating set. Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics. 2022; 71(4): 1023 - 1028. 10.31801/cfsuasmas.1051208
Vancouver Batal A Parity of an odd dominating set. Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics. 2022; 71(4): 1023 - 1028. 10.31801/cfsuasmas.1051208
IEEE Batal A "Parity of an odd dominating set." Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics, 71, ss.1023 - 1028, 2022. 10.31801/cfsuasmas.1051208
ISNAD Batal, Ahmet. "Parity of an odd dominating set". Communications Faculty of Sciences University of Ankara Series A1: Mathematics and Statistics 71/4 (2022), 1023-1028. https://doi.org/10.31801/cfsuasmas.1051208