### 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 μ ≥ -Δ + 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|E|, for all A between 0.845 and 1. This extends a result of Karloff.

Original language | English (US) |
---|---|

Pages (from-to) | 1-12 |

Number of pages | 12 |

Journal | Combinatorics Probability and Computing |

Volume | 9 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2000 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Bipartite Subgraphs and the Smallest Eigenvalue'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Sudakov, B. (2000). Bipartite Subgraphs and the Smallest Eigenvalue.

*Combinatorics Probability and Computing*,*9*(1), 1-12. https://doi.org/10.1017/S0963548399004071