Max k-cut and the smallest eigenvalue

Abstract

Let $G$ be a graph of order $n$ and size $m$, and let ${\mathrm{mc}}_k\left(G\right)$ be the maximum size of a $k$-cut of $G.$ It is shown that \[ \mathrm{mc}_{k}\left( G\right) \leq\frac{k-1}{k}\left( m-\frac{μ_{\min }\left( G\right) n}{2}\right) , \] where ${\mu }_{\min }\left(G\right)$ is the smallest eigenvalue of the adjacency matrix of $G.$ An infinite class of graphs forcing equality in this bound is constructed.

arXiv comment5 pages. Some typos corrected in v2

References in corpus (1)

• New bounds for the max-$k$-cut and chromatic number of a graph