Publication: On monochromatic spectra in graphs
0
0
Issued Date
2015
Resource Type
File Type
application/pdf
ISSN
8353026
Other identifier(s)
2-s2.0-84942465716
Rights Holder(s)
Scopus
Bibliographic Citation
Journal of Combinatorial Mathematics and Combinatorial Computing. Vol 94, (2015), p.97-114
Suggested Citation
Lumduanhom C., Andrews E., Zhang P. On monochromatic spectra in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol 94, (2015), p.97-114. Retrieved from: https://hdl.handle.net/20.500.14740/6220
Author(s)
Abstract
For a nontrivial connected graph G, let c: V(G) → ℤ<inf>2</inf> be a vertex coloring of G where c(v) ≈ 0 for at least one vertex v of G. Then the coloring c induces a new coloring σ: V(G) → ℤ<inf>2</inf> of G defined by σ (v) = Σ<inf>u∞N[v]</inf> c(u) where N[v] is the closed neighborhood of v and addition is performed in ℤ<inf>2</inf>. If σ(v) = 0 ∞ ℤ<inf>2</inf> 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 χ(2,0)(G). For a (2,0)-colorable graph G, the monochromatic (2,0)-spectrum S<inf>(2,0)</inf> (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 ≥ 2 and a ∞ S<inf>(2,0)</inf>(G), then o is even and 1 ≤ |S<inf>(2,0)</inf>(G)| ≤ | n/2]. It is shown that for every pair k, n of integers with 1 ≤ k ≤ [n/2], there is a connected graph G of order n such that |S<inf>(2,0)</inf>(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.