The maximum degree of Nosal graphs

Source abstract

A graph $G$ with $m$ edges is a Nosal graph if its spectral radius $λ(G)$ exceeds $\sqrt m$. At the threshold $λ(G)=\sqrt m$, the star $K_{1,m}$ shows that one vertex can be incident with all $m$ edges. In contrast, Li, Liu and Zhang [J. Combin. Theory Ser. B 179 (2026)] proved that every Nosal graph $G$ with sufficiently many edges satisfies $Δ(G)\le\frac12m+m^{0.99}$, where the constant $\frac12$ is best possible. In this paper, we prove that every Nosal graph $G$ with spectral radius $λ$ satisfies $Δ(G)<m-\frac12(λ-1)(λ-2)$, and hence $Δ(G)<\frac12m+\frac32\sqrt m-1$. Both bounds are sharp up to an additive constant less than $\frac12$: for every $r\ge3$, the complete graph $K_r$ with $\frac12(r^2+r-2)$ pendant vertices attached to one vertex is a Nosal graph with $r^2-1$ edges whose maximum degree lies within $\frac12$ of both bounds. Consequently, the largest maximum degree of a Nosal graph with $r^2-1$ edges is exactly $\frac12(r^2+3r-4)$. The first bound cannot be improved by any positive additive constant: its gap on these graphs is less than $\frac{4}{r+5}$ and tends to zero as $r\to \infty$.