Connected graphs of fixed order and size with maximal Aα-index: The one-dominating-vertex case

作者：Li, Shuchao^*; Tam, Bit-Shun; Yu, Yuantian; Zhao, Qin

来源：Linear Algebra and Its Applications, 2023, 662: 110-135.

DOI：10.1016/j.laa.2023.01.001

• Maximal A(alpha)-index problem
• A(alpha)-matrix
• Maximal graph
• Threshold graph
• Neighborhood equivalence class

For any real number alpha is an element of[0, 1], by the A(alpha)-matrix of a graph G we mean the matrix A(alpha) (G) = alpha D(G) + (1 - alpha)A(G), where A(G) and D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. The largest eigenvalue of A(alpha)(G) is called the A(alpha)-index of G. Chang and Tam (2011) have proved that for every pair of integers n, k with -1 <= k <= n - 3, H-n,H-k, the graph obtained from the star K-1,K-n-1 by joining a vertex of degree 1 to k + 1 other vertices of degree 1, is the unique connected graph that maximizes the Q-index (i.e., the signless Laplacian spectral radius or, equivalently, the A(1/2)-index) over all connected graphs with n vertices and n + k edges. In this paper it is proved that for every pair of integers n, k with -1 <= k <= n - 3, when 1/2 < alpha < 1 or alpha = 1/2 and k not equal 2, the graph H-n,H-k is the unique connected graph that maximizes the A(alpha)-index over all connected graphs with n vertices and n + k edges. This work extends (and also provides an alternative proof for) the above-mentioned result of Chang and Tam. A complete overview of the history of the maximal index problems is also given.