LAPLACIAN EIGENVALUES AND THE MAXIMUM CUT PROBLEM

We introduce and study an eigenvalue upper bound phi(G) on the maximum cut mc (G) of a weighted graph. The function phi(G) has several interesting properties that resemble the behaviour of mc(G). The following results are presented. We show that phi is subadditive with respect to amalgam, and additive with respect to disjoint sum and 1-sum. We prove that phi(G) is never worse that 1. 131 mc(G) for a planar, or more generally, a weakly bipartite graph with nonnegative edge weights. We give a dual characterization of phi(G), and show that phi(G) is computable in polynomial time with an arbitrary precision.