A note on the positive semidefinitness of $A_alpha (G)$


Abstract in English

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 $alphainleft[ 0,1right] $, write $A_{alpha}left( Gright) $ for the matrix [ A_{alpha}left( Gright) =alpha Dleft( Gright) +(1-alpha)Aleft( Gright) . ] Let $alpha_{0}left( Gright) $ be the smallest $alpha$ for which $A_{alpha}(G)$ is positive semidefinite. It is known that $alpha_{0}left( Gright) 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( Gright) =1/2$; (3) if $G$ is $r$-colorable, then $alpha_{0}left( Gright) geq1/r$.

Download