THE PERFORMANCE OF AN EIGENVALUE BOUND ON THE MAX-CUT PROBLEM IN SOME CLASSES OF GRAPHS

The authors earlier introduced a number phi(G), which gives a well-computable upper bound on the maximum bipartite subgraph of a graph or, more generally, on the maximum cut of a weighted graph. In this paper we study the performance of this bound on a large variety of examples from the graph theory. We also present an alternative definition of phi(G) using a graph operation of vertex-splitting. Finally, we present the results of some preliminary computational experiments on randomly generated graphs.