A note on the positive semidefinitness of $A_{\alpha }(G)$

Abstract

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_α\left( G\right) =αD\left( G\right) +(1-α)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)\le 1/2$. The main results of this paper are: (1) if $G$ is $d$-regular then \[ α_{0}=\frac{-λ_{\min}(A(G))}{d-λ_{\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)\ge 1/r$.

7 pages