On the $A_{\alpha}$-spectra of graphs

NEW

Problem: For finite simple connected undirected graphs $G$ of order $n$, define

$$A_\alpha(G)=\alpha D(G)+(1-\alpha)A(G),\qquad \tfrac12<\alpha<1,$$

and let $\lambda_n$ denote the smallest eigenvalue. The conjecture is:

$$\lambda_n(A_\alpha(G))\ge \lambda_n(A_\alpha(K_{1,n-1})),$$

with equality iff $G\cong K_{1,n-1}$. For $n=1$ this is trivial; assume $n\ge2$.

Result: The conjecture is true.

Put $\beta=1-\alpha$. For the star $S_n=K_{1,n-1}$, its least eigenvalue is the smaller root

$$r=\frac{\alpha n-\sqrt{\alpha^2(n-2)^2+4\beta^2(n-1)}}2$$

of

$$(\alpha-r)(\alpha(n-1)-r)=\beta^2(n-1).$$

Thus $0<r<\alpha$. Set

$$a=\alpha-r,\qquad h=\frac r{n-1}.$$

The star equation gives

$$h=\alpha-\frac{\beta^2}{a}.$$

First consider a tree $T$. Since $T$ is bipartite, $A_\alpha(T)$ is orthogonally similar to

$$M_T=\alpha D(T)-\beta A(T)=\beta L(T)+(2\alpha-1)D(T).$$

We prove $M_T-rI\succeq0$.

Root $T$ at a vertex $\rho$. In the usual leaf-elimination Schur complement process, define pivots $f_v$. For a non-root vertex $v$, with children $u$,

$$f_v=\alpha(|C(v)|+1)-r-\sum_{u\in C(v)}\frac{\beta^2}{f_u}.$$

Let $e_v$ be the number of edges in the rooted subtree below $v$. We claim

$$f_v\ge a+e_vh>0.$$

This is clear for leaves. If the children have subtree-edge counts $e_u$, then using induction it is enough to note that for $0\le e\le n-2$,

$$\alpha-\frac{\beta^2}{a+eh}-(e+1)h =\frac{h^2e(n-2-e)}{a+eh}\ge0.$$

Hence

$$f_v\ge a+\sum_{u\in C(v)}(e_u+1)h=a+e_vh.$$

For the root,

$$f_\rho=\alpha|C(\rho)|-r-\sum_{u\in C(\rho)}\frac{\beta^2}{f_u} \ge \sum_{u\in C(\rho)}(e_u+1)h-r =(n-1)h-r=0.$$

Thus all Schur pivots are positive except possibly the final one, so $M_T-rI\succeq0$. Therefore

$$\lambda_n(A_\alpha(T))=\lambda_{\min}(M_T)\ge r.$$

Equality in the displayed inequality occurs only when every child-subtree size $e$ is $0$ or $n-2$. This forces the rooted tree to be a star: either the root is adjacent to all other vertices, or the root has a single child adjacent to all remaining vertices. Hence for trees,

$$\lambda_n(A_\alpha(T))=r \quad\Longleftrightarrow\quad T\cong K_{1,n-1}.$$

Now let $G$ be connected and let $T$ be a spanning tree. For each added edge $uv$,

$$A_\alpha(G)-A_\alpha(T)$$

has on $\{u,v\}$ the block $\begin{pmatrix}\alpha&\beta\\ \beta&\alpha\end{pmatrix}$, whose eigenvalues are $1$ and $2\alpha-1>0$. Hence

$$A_\alpha(G)-A_\alpha(T)\succeq0,$$

so by the variational principle,

$$\lambda_n(A_\alpha(G))\ge \lambda_n(A_\alpha(T))\ge r =\lambda_n(A_\alpha(K_{1,n-1})).$$

If equality holds, then $T$ must be a star. If $G$ had any additional edge, it would join two leaves of that star. The least star eigenvalue $r$ is simple, with eigenvector nonzero and equal on all leaves. The positive definite edge contribution from an added leaf-leaf edge gives strictly positive quadratic form on this eigenvector, contradicting equality. Therefore no extra edge exists and $G\cong K_{1,n-1}$.

Thus the conjecture holds exactly as stated for $n\ge2$, with the $n=1$ case trivial.

Citation: No prior resolution is used here. The conjecture is from Lin, Xue, and Shu, “On the $A_\alpha$-spectra of graphs,” Linear Algebra Appl. 556 (2018), 210–219; arXiv:1709.00182.