A note on the positive semidefinitness of $A_α(G)$

Vladimir Nikiforov, Oscar Rojo

Published 2016-11-06Version 1

Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For every real $\alpha\in\left[ 0,1\right] $, write $A_{\alpha}\left( G\right) $ for the matrix \[ A_{\alpha}\left( G\right) =\alpha D\left( G\right) +(1-\alpha)A\left( G\right) . \] Let $\alpha_{0}\left( G\right) $ be the smallest $\alpha$ for which $A_{\alpha}(G)$ is positive semidefinite. It is known that $\alpha_{0}\left( G\right) \leq1/2$. The main results of this paper are: (1) if $G$ is $d$-regular then \[ \alpha_{0}=\frac{-\lambda_{\min}(A(G))}{d-\lambda_{\min}(A(G))}, \] where $\lambda_{\min}(A(G))$ is the smallest eigenvalue of $A(G)$; (2) $G$ contains a bipartite component if and only if $\alpha_{0}\left( G\right) =1/2$; (3) if $G$ is $r$-colorable, then $\alpha_{0}\left( G\right) \geq1/r$.