Abstract
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.
Keywords
Adjacency matrixCombinatoricsEigenvalues and eigenvectorsGraphComputer scienceDiscrete mathematicsMathematicsPhysics
Affiliated Institutions
Related Publications
The Best Two Independent Measurements Are Not the Two Best
Consider an item that belongs to one of two classes, θ = 0 or θ = 1, with equal probability. Suppose also that there are two measurement experiments E <sub xmlns:mml="http://www...
On the Capacity of Radio Communication Systems with Diversity in a Rayleigh Fading Environment
In this paper, we study the fundamental limits on the data rate of multiple antenna systems in a Rayleigh fading environment. With <tex xmlns:mml="http://www.w3.org/1998/Math/Ma...
Low-density parity-check codes
A low-density parity-check code is a code specified by a parity-check matrix with the following properties: each column contains a small fixed number <tex xmlns:mml="http://www....
Compressed sensing
Suppose x is an unknown vector in Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> (a digital image or signal); we pla...
Communication Theory of Secrecy Systems*
THE problems of cryptography and secrecy systems furnish an interesting application of communication theory. <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="htt...
Publication Info
- Year
- 1973
- Type
- article
- Volume
- 17
- Issue
- 5
- Pages
- 420-425
- Citations
- 650
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
650
OpenAlex
Cite This
W. E. Donath,
Alan J. Hoffman
(1973).
Lower Bounds for the Partitioning of Graphs.
IBM Journal of Research and Development
, 17
(5)
, 420-425.
https://doi.org/10.1147/rd.175.0420
Identifiers
- DOI
- 10.1147/rd.175.0420