The maximum degree of Nosal graphs
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality