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) \neq 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 \geq 2 \) and \( a \in S_{(2,0)}(G) \), then \( a \) is even and \( 1 \leq |S_{(2,0)}(G)| \leq \left\lfloor \frac{n}{2} \right\rfloor \). It is shown that for every pair \( k,n \) of integers with \( 1 \leq k \leq \left\lfloor \frac{n}{2} \right\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.