pith. sign in

arxiv: 1604.02088 · v2 · pith:XHAMSIPUnew · submitted 2016-04-07 · 🧮 math.CO

Max k-cut and the smallest eigenvalue

classification 🧮 math.CO
keywords leftrighteigenvaluefracmathrmsizesmallestadjacency
0
0 comments X
read the original abstract

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

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.