Local bipartite turán graphs and graph partitioning
Jon Lee, Jennifer Ryan · Networks · 1994
Abstract Motivated by the NP‐hard problem of finding a minimum‐weight balanced bipartition of an edge‐weighted complete graph, we studied the class of graphs having the same degrees as bipartite Turán graphs. In particular, we established a maximal set of linear equations satisfied by the counts of the possible incidences of 3‐ and 4‐cycles on such graphs. This leads to extremal results that we exploit in a heuristic for the partitioning problem, as well as in the computation of a Lagrangian bound. Preliminary computational results with the heuristic appear to be quite promising. Further results are established linking various adjacency concepts and measures of nonbipartiteness for such graphs. We also demonstrate the potential power of the Lagrangian bound via a family of examples. © 1994 by John Wiley & Sons, Inc.