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 inter esting 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 prov e that phi(G) is never worse that 1. 131 mc(G) for a planar, or more g enerally, a weakly bipartite graph with nonnegative edge weights. We g ive a dual characterization of phi(G), and show that phi(G) is computa ble in polynomial time with an arbitrary precision.