Max k-cut and the smallest eigenvalue

DOI10.1016/J.LAA.2016.04.019zbMATH Open1338.05168arXiv1604.02088OpenAlexW2964166578MaRDI QIDQ286169FDOQ286169

Authors: Vladimir Nikiforov 

Publication date: 20 May 2016

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Laplacian eigenvalues and the maximum cut problem
• Title not available (Why is that?)
• Max cut and the smallest eigenvalue
• Title not available (Why is that?)
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• Chromatic number and spectral radius

Cited In (9)

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

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)