Nonregular graphs of odd maximum degree with maximum spectral radius

Abstract

Let $\rho (n,d)$ denote the maximum adjacency spectral radius among all connected nonregular graphs of order $n$ and maximum degree $d$. A graph attaining this maximum is called an extremal graph. Liu [J. Combin. Theory Ser. B, 2024] determined the extremal graphs for $d=3,4$ and formulated two conjectures for general $d$. For each fixed odd integer $d\ge 3$, the conjectures assert that: (1) $\underset{n\to \infty }{\lim }{n}^2(d-\rho (n,d))=(d-1){\pi }^2/4$. (2) For all sufficiently large $n$, the degree sequence of every extremal graph is $(d,\dots ,d,d-1)$ for odd $n$ and $(d,\dots ,d,1)$ for even $n$. We prove the first conjecture for every fixed odd $d\ge 3$ and, more precisely, obtain the asymptotic expansion \[ ρ(n,d) =d-\frac{(d-1)π^2}{4n^2} +\frac{(d-1)^2π^2}{4n^3} +O_d(n^{-4}) \qquad(n\to\infty). \] We further prove the second conjecture for every fixed odd $d\ge 3$.

arXiv comment25 pages