Let G be a graph with adjacency matrix A(G) and let D(G) be the diagonal matrix of degrees of G. For \(\alpha \in [0,1]\) , Nikiforov (Appl Anal Discrete Math 11(1): 81–107, 2017) introduced the family of matrices \(A_\alpha (G)=\alpha D(G) + (1-\alpha )A(G)\) , together with fundamental properties and several open problems. From such properties, it follows that there exists a unique \(\alpha _0(G)\) such that \(A_{\alpha }(G)\) is positive semidefinite for all \(\alpha \ge \alpha _0\) . One of the problems is: Given a graph G, find \(\alpha _0(G)\) . We call it the \(\alpha _0\) -Nikiforov’s problem. In this work, we give a fundamental result on \(\alpha _0(G)\) . Moreover, if \(B_k({\textbf {d}})\) is a generalized Bethe tree of k levels with \({\textbf {d}}=(d_1,d_2,\ldots ,d_k)\) where, for \(1\le j\le k\) , \(d_j\) is the degree of the vertices at the level \(k-j+1\) , we study the positive semidefiniteness of \(A_{\alpha }(G)\) and the computation of \({\alpha _0}(G)\) for the following classes of graphs:
1. \(G=R\{rB_k({\textbf {d}})\}\) is the graph obtained from r copies of \(B_k({\textbf {d}})\) and an arbitrary connected nonbipartite graph R of order r by identifying the root of each copy of \(B_k({\textbf {d}})\) with a different vertex of R.
2. \(G=K_r\{pB_k({\textbf {d}})\}\) , \(1\le p \le r\) , is the graph obtained from p copies of \(B_k({\textbf {d}})\) and the complete graph \(K_r\) , \(r \ge 3\) , by identifying the root of each copy of \(B_k({\textbf {d}})\) with a different vertex of \(K_r\) .
The computation of \(\alpha _0(G)\) is performed by first computing the determinant of a symmetric tridiagonal matrix of order k or \(k+1\) . Using the three-term recursion formula for this class of matrices, the cost of computing the determinant is linear. Moreover, we give the \(A_\alpha \) -spectra of the above mentioned classes of graphs in terms of the eigenvalues of symmetric tridiagonal matrices of order less than or equal to k or \(k+1\) .
