The maximum degree of Nosal graphs

arXiv:2610.40380 · math.CO · Submitted 2026-10-29 · Read on arXiv

math.CO

Submitted: 2026-10-29

Updated: 2026-10-29

Comments: 6 pages, 1 figure. Any comments are welcome

License: http://creativecommons.org/licenses/by/4.0/

The gist: A graph G with m edges is a Nosal graph if its spectral radius λ(G) exceeds sqrt m.

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) at most 12m+m 0.99, where the constant 12 is best possible. In this paper, we prove that every Nosal graph G with spectral radius λ satisfies Δ(G)<m- 12(λ-1)(λ-2), and hence Δ(G)< 12m+ 32 sqrt m-1. Both bounds are sharp up to an additive constant less than 12: for every r at least3, the complete graph K r with 12(r 2+r-2) pendant vertices attached to one vertex is a Nosal graph with r 2-1 edges whose maximum degree lies within 12 of both bounds. Consequently, the largest maximum degree of a Nosal graph with r 2-1 edges is exactly 12(r 2+3r-4). The first bound cannot be improved by any positive additive constant: its gap on these graphs is less than 4 over r+5 and tends to zero as r to infinity.

Related papers