Nonregular graphs of odd maximum degree with maximum spectral radius
Abstract
Let ρ(n,d) denote the maximum adjacency spectral radius among all connected nonregular graphs of order n and maximum degree d. A graph attaining this maximum is called an extremal graph. Liu [J. Combin. Theory Ser. B, 2024] determined the extremal graphs for d=3,4 and formulated two conjectures for general d. For each fixed odd integer d≥3, the conjectures assert that: (1) limn→∞n2(d−ρ(n,d)) =(d−1)π2/4. (2) For all sufficiently large n, the degree sequence of every extremal graph is (d,…,d,d−1) for odd n and (d,…,d,1) for even n. We prove the first conjecture for every fixed odd d≥3 and, more precisely, obtain the asymptotic expansion ρ(n,d) =d−((d−1)π2)/4n2 +((d−1)2π2)/4n3 +Od(n−4) (n→∞). We further prove the second conjecture for every fixed odd d≥3.
Related
- Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
- Asymptotic maximum spectral radius of nonregular graphs
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Minimum Distance Spectral Radius of Tree with Given Maximum Degree
- The maximum spectral radius of connected graphs with prescribed order and size
BibTeX
@misc{fan2026nonregular,
title = {{Nonregular graphs of odd maximum degree with maximum spectral radius}},
author = {Liangdong Fan and Liying Kang and Yaojun Chen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28706},
eprint = {2609.28706},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28706},
}
RIS
TY - UNPB
TI - Nonregular graphs of odd maximum degree with maximum spectral radius
AU - Liangdong Fan
AU - Liying Kang
AU - Yaojun Chen
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28706
UR - https://arxiv.org/abs/2609.28706
AB - Let ρ(n,d) denote the maximum adjacency spectral radius among all connected nonregular graphs of order n and maximum degree d. A graph attaining this maximum is called an extremal graph. Liu [J. Combin. Theory Ser. B, 2024] determined the extremal graphs for d=3,4 and formulated two conjectures for general d. For each fixed odd integer d≥3, the conjectures assert that: (1) lim_n→∞n^2(d−ρ(n,d)) =(d−1)π^2/4. (2) For all sufficiently large n, the degree sequence of every extremal graph is (d,…,d,d−1) for odd n and (d,…,d,1) for even n. We prove the first conjecture for every fixed odd d≥3 and, more precisely, obtain the asymptotic expansion ρ(n,d) =d−((d−1)π^2)/4n^2 +((d−1)^2π^2)/4n^3 +O_d(n^−4) (n→∞). We further prove the second conjecture for every fixed odd d≥3.
ER -