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 <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> ≥ m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> , …, ≥ m <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</inf> vertices. Let E <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">c</inf> be the number of edges whose two vertices belong to different subsets. Let λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> ≥ λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> , …, ≥ λ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</inf> 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.