Extremal spectral radius of nonregular graphs with prescribed maximum degree

Let $G$ be a graph attaining the maximum spectral radius among all connected nonregular graphs of order $n$ with maximum degree $Δ$. Let $λ_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 $Δ$. Concerning an important structural property of the extremal graphs $G$, Liu and Li present another conjecture which states that $G$ has degree sequence $Δ,\ldots,Δ,δ$. Here, $δ=Δ-1$ or $δ=Δ-2$ depending on the parity of $nΔ$. In this paper, we make progress on the two conjectures. To be precise, we disprove the first conjecture for all $Δ\geq 3$ by showing that the limit superior is at most $π^2/2$. For small $Δ$, we determine the precise asymptotic behavior of $Δ-λ_1(G)$. In particular, we show that $\lim\limits_{n\to\infty} n^2 (Δ- λ_1(G)) /(Δ- 1) = π^2/4$ if $Δ=3$; and $\lim\limits_{n\to\infty} n^2 (Δ- λ_1(G)) /(Δ- 2) = π^2/2$ if $Δ= 4$. We also confirm the second conjecture for $Δ= 3$ and $Δ= 4$ by determining the precise structure of extremal graphs. Particularly, we show that the extremal graphs for $Δ\in\{3,4\}$ must have a path-like structure built from specific blocks.

No reviews yet.

No comments yet.