The maximum degree of Nosal graphs
Abstract
A graph G with m edges is a Nosal graph if its spectral radius λ(G) exceeds √m. At the threshold λ(G)=√m, the star K1,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)≤1/2m+m0.99, where the constant 1/2 is best possible. In this paper, we prove that every Nosal graph G with spectral radius λ satisfies Δ(G)<m−1/2(λ−1)(λ−2), and hence Δ(G)<1/2m+3/2√m−1. Both bounds are sharp up to an additive constant less than 1/2: for every r≥3, the complete graph Kr with 1/2(r2+r−2) pendant vertices attached to one vertex is a Nosal graph with r2−1 edges whose maximum degree lies within 1/2 of both bounds. Consequently, the largest maximum degree of a Nosal graph with r2−1 edges is exactly 1/2(r2+3r−4). The first bound cannot be improved by any positive additive constant: its gap on these graphs is less than 4/(r+5) and tends to zero as r→ ∞.
Related
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
- Strong edge coloring of graphs with maximum degree $6$
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- Treedepth is NP-Hard on Planar Graphs of Maximum Degree 3
BibTeX
@misc{li2026maximum,
title = {{The maximum degree of Nosal graphs}},
author = {Yongtao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40380},
eprint = {2610.40380},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40380},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The maximum degree of Nosal graphs
AU - Yongtao Li
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40380
UR - https://arxiv.org/abs/2610.40380
AB - A graph G with m edges is a Nosal graph if its spectral radius λ(G) exceeds √m. At the threshold λ(G)=√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)≤1/2m+m^0.99, where the constant 1/2 is best possible. In this paper, we prove that every Nosal graph G with spectral radius λ satisfies Δ(G)<m−1/2(λ−1)(λ−2), and hence Δ(G)<1/2m+3/2√m−1. Both bounds are sharp up to an additive constant less than 1/2: for every r≥3, the complete graph K_r with 1/2(r^2+r−2) pendant vertices attached to one vertex is a Nosal graph with r^2−1 edges whose maximum degree lies within 1/2 of both bounds. Consequently, the largest maximum degree of a Nosal graph with r^2−1 edges is exactly 1/2(r^2+3r−4). The first bound cannot be improved by any positive additive constant: its gap on these graphs is less than 4/(r+5) and tends to zero as r→ ∞.
ER -