On Monochromatic Spectra in Graphs

Abstract

For a nontrivial connected graph $G$, let $c:V(G)\to {\mathbb{Z}}_2$ be a vertex coloring of $G$ where $c(v)\ne 0$ for at least one vertex $v$ of $G$. Then the coloring $c$ induces a new coloring $\sigma :V(G)\to {\mathbb{Z}}_2$ of $G$ defined by
$$\sigma (v)=\sum _{u\in N[v]}c(u)$$
where $N[v]$ is the closed neighborhood of $v$ and addition is performed in ${\mathbb{Z}}_2$. If $\sigma (v)=0\in {\mathbb{Z}}_2$ for every vertex $v$ in $G$, then the coloring $c$ is called a (modular) monochromatic $(2,0)$-coloring of $G$. A graph $G$ having a monochromatic $(2,0)$-coloring is a (monochromatic) $(2,0)$-colorable graph. The minimum number of vertices colored $1$ in a monochromatic $(2,0)$-coloring of $G$ is the $(2,0)$-chromatic number of $G$ and is denoted by ${\chi }_{(2,0)}(G)$. For a $(2,0)$-colorable graph $G$, the monochromatic $(2,0)$-spectrum $S_{(2,0)}(G)$ of $G$ is the set of all positive integers $k$ for which exactly $k$ vertices of $G$ can be colored $1$ in a monochromatic $(2,0)$-coloring of $G$. Monochromatic $(2,0)$-spectra are determined for several well-known classes of graphs. If $G$ is a connected graph of order $n\ge 2$ and $a\in S_{(2,0)}(G)$, then $a$ is even and $1\le |S_{(2,0)}(G)|\le \lfloor \frac{n}{2}\rfloor$. It is shown that for every pair $k,n$ of integers with $1\le k\le \lfloor \frac{n}{2}\rfloor$, there is a connected graph $G$ of order $n$ such that $|S_{(2,0)}(G)|=k$. A set $S$ of positive even integers is $(2,0)$-realizable if $S$ is the monochromatic $(2,0)$-spectrum of some connected graph. Although there are infinitely many non-$(2,0)$-realizable sets, it is shown that every set of positive even integers is a subset of some $(2,0)$-realizable set. Other results and questions are also presented on $(2,0)$-realizable sets in graphs.