On the maximal Aa -index of graphs with a prescribed number of edges
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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2025-05-01
|
| Series: | Special Matrices |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/spma-2025-0036 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849310343993491456 |
|---|---|
| author | Chang Ting-Chung Tam Bit-Shun |
| author_facet | Chang Ting-Chung Tam Bit-Shun |
| author_sort | Chang Ting-Chung |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-1add83195ffb4beea52b1749658e7887 |
| institution | Kabale University |
| issn | 2300-7451 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Special Matrices |
| spelling | doaj-art-1add83195ffb4beea52b1749658e78872025-08-20T03:53:46ZengDe GruyterSpecial Matrices2300-74512025-05-011319722010.1515/spma-2025-0036On the maximal Aa -index of graphs with a prescribed number of edgesChang Ting-Chung0Tam Bit-Shun1Chihlee University of Technology, New Taipei City 220305, Taiwan, Republic of ChinaDepartment of Applied Mathematics and Data Science, Tamkang University, New Taipei City 25137, Taiwan, Republic of ChinaFor 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.https://doi.org/10.1515/spma-2025-0036maximal aα-index problemmaximal graphthreshold graphneighborhood equivalence classesquasi-complete graphsquasi-stars05c3505c50 |
| spellingShingle | Chang Ting-Chung Tam Bit-Shun On the maximal Aa -index of graphs with a prescribed number of edges Special Matrices maximal aα-index problem maximal graph threshold graph neighborhood equivalence classes quasi-complete graphs quasi-stars 05c35 05c50 |
| title | On the maximal Aa
-index of graphs with a prescribed number of edges |
| title_full | On the maximal Aa
-index of graphs with a prescribed number of edges |
| title_fullStr | On the maximal Aa
-index of graphs with a prescribed number of edges |
| title_full_unstemmed | On the maximal Aa
-index of graphs with a prescribed number of edges |
| title_short | On the maximal Aa
-index of graphs with a prescribed number of edges |
| title_sort | on the maximal aa index of graphs with a prescribed number of edges |
| topic | maximal aα-index problem maximal graph threshold graph neighborhood equivalence classes quasi-complete graphs quasi-stars 05c35 05c50 |
| url | https://doi.org/10.1515/spma-2025-0036 |
| work_keys_str_mv | AT changtingchung onthemaximalaaindexofgraphswithaprescribednumberofedges AT tambitshun onthemaximalaaindexofgraphswithaprescribednumberofedges |