An \(A_\alpha\)-spectral version of the Bhattacharya-Friedland-Peled conjecture

Yuantian Yu ; Xianya Geng¹ ; Shuchao Li

¹Anhui university of science and technology

The electronic journal of combinatorics, Tome 31 (2024) no. 4

Résumé

In 1985, Brualdi and Hoffman posed the following conjecture: Let $G$ be an $n$-vertex graph of size $m,$ where $0\leq m\leq\binom{n}{2}.$ If $m=\binom{a}{2}+b$ with $0\leq b<a,$ then $G\cong (K_b\vee(K_{a-b}\cup K_1))\cup(n-a-1)K_1$ is the unique graph having the largest spectral radius. This conjecture was completely resolved by Rowlinson (1988). In 2018, Bhattacharya, Friedland and Peled posed the bipartite version of Brualdi-Hoffman conjecture. Here, we consider an $A_\alpha$-spectral extremal question, which may be seen as an $A_\alpha$-spectral version of the Bhattacharya-Friedland-Peled conjecture: For fixed $\alpha\in [0,1),$ which graph attains the maximum $A_\alpha$-index over all bipartite graphs with $n$ vertices and $m$ edges? When $\frac{1}{2}\leq\alpha<1$, we prove that for every pair of positive integers $n,\,m,$ if $m=k(n-k)$, where $k$ is a positive integer with $k\neq 1,n-1$, then the complete bipartite graph $K_{k,n-k}$ is the unique graph that maximizes the $A_\alpha$-index over all bipartite graphs with $n$ vertices and $m$ edges; if $n\leq m\leq 2n-5$, then $K_{2,n-2}^m,$ the graph obtained from the complete bipartite graph $K_{2,n-2}$ by deleting $2n-4-m$ edges which are incident on a common vertex of degree $n-2$, is the unique graph that maximizes the $A_\alpha$-index over all bipartite graphs with $n$ vertices and $m$ edges; if $2n-3\leq m\leq 2\sqrt{2}(n-4),$ then $K_{3,n-3}^m,$ the graph obtained from the complete bipartite graph $K_{3,n-3}$ by deleting $3n-9-m$ edges which are incident on a common vertex of degree $n-3$, is the unique graph that maximizes the $A_\alpha$-index over all bipartite graphs with $n$ vertices and $m$ edges. It improves some known ones of Zhang and Li (2017) and partially answer some questions posed by Zhai, Lin and Zhao (2022).

Détail

DOI : 10.37236/12211

Classification : 05C50, 05C35
Mots-clés : extremal graph, bipartite graph, signless Laplacian matrix, \(Q\)-index