Special Matrices (May 2025)
On the maximal Aa -index of graphs with a prescribed number of edges
Abstract
For any real number α∈[0,1]\alpha \in \left[\mathrm{0,1}], by the Aα{A}_{\alpha }-matrix of a graph GG, we mean the matrix Aα(G)=αD(G)+(1−α)A(G){A}_{\alpha }\left(G)=\alpha D\left(G)+\left(1-\alpha )A\left(G), where A(G)A\left(G) and D(G)D\left(G) are the adjacency matrix and the diagonal matrix of vertex degrees of GG, respectively. The largest eigenvalue of Aα(G){A}_{\alpha }\left(G) is called the Aα{A}_{\alpha }-index of GG. Chang and Tam (Graphs of fixed order and size with maximal-index, Linear Algebra Appl. 673 (2023), 69–100) have solved the problem of determining graphs with maximal Aα{A}_{\alpha }-index over G(n,m){\mathcal{G}}\left(n,m), the class of graphs with nn vertices and mm edges, for α∈12,1\alpha \in \left[\phantom{\rule[-0.75em]{}{0ex}},\frac{1}{2},1\right) and 1≤m≤2n−31\le m\le 2n-3. In the same article, they posed the problem of characterizing graphs in G(n,m){\mathcal{G}}\left(n,m) that maximize the Aα{A}_{\alpha }-index for 0<α<120\lt \alpha \lt \frac{1}{2} and m≤n−1m\le n-1. In this study, it is noted that, for any α∈\alpha \hspace{0.33em}\in [0, 1), the problem of characterizing graphs with maximal Aα{A}_{\alpha }-index over G(n,m){\mathcal{G}}\left(n,m) with m≤n−1m\le n-1 is equivalent to the problem of characterizing graphs with maximal Aα{A}_{\alpha }-index over S(m){\mathscr{S}}\left(m), the class of graphs with mm edges. In connection with the latter problem, we pose the following conjecture: Let m≥3m\ge 3 be a positive integer and suppose that m=d2+tm=\left(\phantom{\rule[-0.75em]{}{0ex}},\genfrac{}{}{0ex}{}{d}{2}\right)+t with 0≤t<d0\le t\lt d. There exists a real number α0{\alpha }_{0}, α0=12{\alpha }_{0}=\frac{1}{2} for m=3m=3 and α0∈[0,12){\alpha }_{0}\in \left[0,\frac{1}{2}) for m≥4m\ge 4, such that for any α∈\alpha \hspace{0.33em}\in [0, 1), Cd+1m{C}_{d+1}^{m} (replaced by Kd{K}_{d}, in case t=0t=0), where Cnm{C}_{n}^{m} denotes the quasi-complete graph with nn vertices and mm edges, or K1,m{K}_{1,m} is the unique connected graph with mm edges that maximize the Aα{A}_{\alpha }-index over S(m){\mathscr{S}}\left(m), depending on whether α∈[0,α0)\alpha \in \left[0,{\alpha }_{0}) or α∈(α0,1)\alpha \in \left({\alpha }_{0},1); when α=α0\alpha ={\alpha }_{0}, there are exactly two connected graphs that maximize the Aα{A}_{\alpha }-index over S(m){\mathscr{S}}\left(m), namely, Cd+1m{C}_{d+1}^{m} (or Kd{K}_{d}, in case t=0t=0) and K1,m{K}_{1,m}. The conjecture is established when t=0t=0.
Keywords
