Conjectured lower bound for the clique number of a graph

MaRDI QIDQ6300192zbMATH OpenFDO

Authors Clive Elphick, Pawel Wocjan

Publication date 10 April 2018

Abstract: It is well known that $n/(n-mu)$, where $mu$ is the spectral radius of a graph with $n$ vertices, is a lower bound for the clique number. We conjecture that $mu$ can be replaced in this bound with $sqrt{s}^{+}$, where $s^{+}$ is the sum of the squares of the positive eigenvalues. We prove this conjecture for various classes of graphs, including triangle-free graphs, and for almost all graphs.

This page was built for publication: Conjectured lower bound for the clique number of a graph

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