Lower Bounds for the Partitioning of Graphs

Publisher Website
Google Scholar
Abstract
Let a k-partition of a graph be a division of the vertices into k disjoint subsets containing m1 ≥ m2,..., ≥mk vertices. Let Ec 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 suomf all the elements of the sum matrix is zero. Then Ec ≥ 1/2Σr=1k-mrλr. 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.C omputational studies are madoef the ratio of upper bound to lower bound for the two-partition of a number of random graphs having up to 100 nodes.

This publication has 0 references indexed in Scilit: