Max k-cut and the smallest eigenvalue

الأصل · EN

Let G be a graph of order n and size m, and let mcₖ(G) be the maximum size of a k-cut of G. It is shown that mcₖ(G) ≤k-1/k(m-μ(G) n2), where μ(G) is the smallest eigenvalue of the adjacency matrix of G. An infinite class of graphs forcing equality in this bound is constructed.