Max k-cut and the smallest eigenvalue

DOI10.1016/J.LAA.2016.04.019MaRDI QIDQ286169zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 20 May 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.02088

zbMATH Keywords

chromatic number\(\max k\)-cutlargest eigenvalueslargest Laplacian eigenvaluesmallest adjacency eigenvalue

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Let $G$ be a graph of order $n$ and size $m$, and let $mathrm{mc}_{k}left(Gight)$ be the maximum size of a $k$-cut of $G.$ It is shown that [ mathrm{mc}_{k}left( G ight) leqfrac{k-1}{k}left( m-frac{mu_{min }left( G ight) n}{2} ight) , ] where $m{u}_{min}left(Gight)$ is the smallest eigenvalue of the adjacency matrix of $G.$ An infinite class of graphs forcing equality in this bound is constructed.

Recommendations

• scientific article; zbMATH DE number 4193718
• A class of spectral bounds for max \(k\)-cut
• Bound on the least eigenvalue of a graph with cut vertices
• On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
• Bounds on the eigenvalues of graphs with cut vertices or edges

Cites work

• scientific article; zbMATH DE number 1944141 (Why is no real title available?)
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• Chromatic number and spectral radius
• Laplacian eigenvalues and the maximum cut problem
• Max cut and the smallest eigenvalue
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph

Cited in

(9)

• Computational study of valid inequalities for the maximum \(k\)-cut problem
• Laplacian eigenvalues and the maximum cut problem
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Minimum cuts, girth and a spectral threshold
• Combinatorial upper bounds for the smallest eigenvalue of a graph
• A spectral partitioning algorithm for maximum directed cut problem
• On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem
• A class of spectral bounds for max \(k\)-cut
• An inequality for eigenvalues of symmetric matrices with applications to max-cuts and Graph Energy^∗

This page was built for publication: Max \(k\)-cut and the smallest eigenvalue

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q286169)