Lower Bounds for the Partitioning of Graphs

Let a k-partition of a graph be a division of the vertices into k disjoint subsets containing m 1 ≥ m 2 , …, ≥ m k vertices. Let E c be the number of edges whose two vertices belong to different subsets. Let λ 1 ≥ λ 2 , …, ≥ λ k be 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.