Metraipolis › archive › dc_aff90c42b70e

The maximum degree of Nosal graphs — arXiv:2610.40380

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40380
License (as archived)
CC0-1.0
Archived
2026-11-01T02:38:07.007Z
SHA-256 of the archived text
60f6628425a788a9c9132fa7886020824280d9af88a10444a7ffa69f00938e34
Stable URL of this page
https://metraipolis.com/documento/dc_aff90c42b70e

How to cite

The maximum degree of Nosal graphs — arXiv:2610.40380 — arXiv (en), https://arxiv.org/abs/2610.40380 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_aff90c42b70e (Metraipolis archive dc_aff90c42b70e, sha256 60f6628425a788a9c9132fa7886020824280d9af88a10444a7ffa69f00938e34)
BibTeX
@misc{dcaff90c42b70e,
  title = {The maximum degree of Nosal graphs — arXiv:2610.40380},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40380},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_aff90c42b70e; sha256 60f6628425a788a9c9132fa7886020824280d9af88a10444a7ffa69f00938e34},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40380. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A graph $G$ with $m$ edges is a Nosal graph if its spectral radius $\lambda(G)$ exceeds $\sqrt m$. At the threshold $\lambda(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 $\Delta(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 $\lambda$ satisfies $\Delta(G)<m-\frac12(\lambda-1)(\lambda-2)$, and hence $\Delta(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$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.40380 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.294Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).