Bipartite Subgraphs and the Smallest Eigenvalue
- 1 January 2000
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 9 (1) , 1-12
- https://doi.org/10.1017/s0963548399004071
Abstract
Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue μ of any non-bipartite graph on n vertices with diameter D and maximum degree Δ satisfies μ [ges ] −Δ + 1/(D+1)n. This improves previous estimates and is tight up to a constant factor. The second result is the determination of the precise approximation guarantee of the MAX CUT algorithm of Goemans and Williamson for graphs G = (V, E) in which the size of the max cut is at least A[mid ]E[mid ], for all A between 0.845 and 1. This extends a result of Karloff.Keywords
This publication has 0 references indexed in Scilit: