Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T08:32:19.440Z Has data issue: false hasContentIssue false

Bipartite Subgraphs and the Smallest Eigenvalue

Published online by Cambridge University Press:  01 January 2000

NOGA ALON
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: noga@math.tau.ac.il)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: sudakov@math.tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
2000 Cambridge University Press