Parity of an odd dominating set

Authors : Ahmet BATAL

Pages : 1023-1028

Doi:10.31801/cfsuasmas.1051208

View : 20 | Download : 11

Publication Date : 2022-12-30

Article Type : Research Paper

Abstract :For a simple graph $G$ with vertex set $Vinsert ignore into journalissuearticles values(G);=\\{v_1,...,v_n\\}$, we define the closed neighborhood set of a vertex $u$ as \\\\$N[u]=\\{v \\in Vinsert ignore into journalissuearticles values(G); \\; | \\; v \\; \\text{is adjacent to} \\; u \\; \\text{or} \\; v=u \\}$ and the closed neighborhood matrix $Ninsert ignore into journalissuearticles values(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 Vinsert ignore into journalissuearticles values(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 $Ninsert ignore into journalissuearticles values(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