Lower Bounds for the Partitioning of Graphs
Wilm E. Donath, Alan J. Hoffman · IBM Journal of Research and Development · 1973
Let a k-partition of a graph be a division of the vertices into k disjoint subsets containing m1≥ m2, …, ≥ mkvertices. Let Ecbe the number of edges whose two vertices belong to different subsets. Let λ1≥ λ2, …, ≥ λkbe the k largest eigenvalues of a matrix, which is the sum of the adjacency matrix of the graph plus any diagonal matrix U such that the sum of all the elements of the sum matrix is zero. Then given equation. A theorem is given that shows the effect of the maximum degree of any node being limited, and it is also shown that the right-hand side is a concave function of U. Computational studies are made of the ratio of upper bound to lower bound for the two-partition of a number of random graphs having up to 100 nodes.