Bipartite Subgraphs and the Smallest Eigenvalue

DOI10.1017/S0963548399004071zbMath0945.05041WikidataQ127770736 ScholiaQ127770736MaRDI QIDQ4948041

Noga Alon, Benjamin Sudakov

Publication date: 8 October 2000

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

eigenvaluediametermaximum degreemax cut algorithm

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the optimality of the random hyperplane rounding technique for MAX CUT ⋮ On computational capabilities of Ising machines based on nonlinear oscillators ⋮ Extreme eigenvalues of nonregular graphs ⋮ A spectral bound for vertex-transitive graphs and their spanning subgraphs ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ Max-cut and extendability of matchings in distance-regular graphs ⋮ Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ Anti-modularity and anti-community detecting in complex networks ⋮ The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters ⋮ Some observations on the smallest adjacency eigenvalue of a graph ⋮ Randomized diffusion for indivisible loads ⋮ The extreme eigenvalues and maximum degree of \(k\)-connected irregular graphs ⋮ Spectral bounds for the maximum cut problem ⋮ The spectral radius of irregular graphs ⋮ Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians ⋮ On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs ⋮ On the α-spectral radius of graphs