Extremal spectral radius of nonregular graphs with prescribed maximum degree

Abstract

Let $G$ be a graph attaining the maximum spectral radius among all connected nonregular graphs of order $n$ with maximum degree $\Delta$. Let ${\lambda }_1(G)$ be the spectral radius of $G$. A nice conjecture due to Liu, Shen and Wang [On the largest eigenvalue of non-regular graphs, J. Combin. Theory Ser. B, 97 (2007) 1010--1018] asserts that \[ \lim_{n\to\infty} \frac{n^2(Δ-λ_1(G))}{Δ-1} = π^2 \] for each fixed $\Delta$. Concerning an important structural property of the extremal graphs $G$, Liu and Li present another conjecture which states that $G$ has degree sequence $\Delta ,\dots ,\Delta ,\delta$. Here, $\delta =\Delta -1$ or $\delta =\Delta -2$ depending on the parity of $n\Delta$. In this paper, we make progress on the two conjectures. To be precise, we disprove the first conjecture for all $\Delta \ge 3$ by showing that the limit superior is at most ${\pi }^2/2$. For small $\Delta$, we determine the precise asymptotic behavior of $\Delta -{\lambda }_1(G)$. In particular, we show that $\underset{n\to \infty }{\lim }{n}^2(\Delta -{\lambda }_1(G))/(\Delta -1)={\pi }^2/4$ if $\Delta =3$; and $\underset{n\to \infty }{\lim }{n}^2(\Delta -{\lambda }_1(G))/(\Delta -2)={\pi }^2/2$ if $\Delta =4$. We also confirm the second conjecture for $\Delta =3$ and $\Delta =4$ by determining the precise structure of extremal graphs. Particularly, we show that the extremal graphs for $\Delta \in \{3,4\}$ must have a path-like structure built from specific blocks.

36 pages