A connection between the $A_{\alpha }$-spectrum and the Lovász theta number

Abstract

We show that the smallest $\alpha$ so that $\alpha D+(1-\alpha )A\succcurlyeq 0$ is at least $1/\vartheta (\overline{G})$, significantly improving upon a result due to Nikiforov and Rojo (2017). In fact, we display an even stronger connection: if the nonzero entries of $A$ are allowed to vary and those of $D$ vary accordingly, then we show that this smallest $\alpha$ is in fact equal to $1/\vartheta (\overline{G})$. We also show other results obtained as an application of this optimization framework, including a connection to the well-known quadratic formulation for $\omega (G)$ due to Motzkin and Straus (1964).