Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 39 min ago
PreprintarXiv licencearXiv

The maximum spectral radius of connected graphs with prescribed order and size

  • Dragan Stevanović
Open at sourcePDFDOICite

Abstract

In 1986, Brualdi and Solheid asked which connected graph of prescribed order and size has maximum adjacency spectral radius. We complete the classification for every feasible pair of parameters. We prove that no graph outside the dense and star threshold families is extremal, including at ties, and settle the range n≤ e+1, where the star candidate is not defined. The final comparison \emph{between} the dense and star candidates is supplied by Damnjanović's Propositions~4.1--4.2, not reproved here. We combine an exact Bellman recursion with dense-core domination, fractional complete-split bounds, and a virtual-star inequality. Three remaining comparison families (J), (K1), and (K2) are established analytically and by exact polynomial and Sturm certificates. The exact certificates are implemented in Python/SymPy and SageMath.

Related

  1. Connected graphs having maximum signless Laplacian spectral radius
    Di-Jian Wang, Hong-Yan Ge, Shi-Cai Gong +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
    Zejun Huang, Chenxi Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Extremal Graphs with Prescribed Parameters for the Spectral Radius of Weighted Adjacency Matrices with Property P∗
    Swathi Shetty, B. R. Rakshith, Sayinath Udupa N. V
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Asymptotic maximum spectral radius of nonregular graphs
    Hangxi Cha, Haiying Shan
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Extremal spectral radius of nonregular graphs with a fixed odd maximum degree
    Zejun Huang, Chenxi Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{stevanovic2026maximum,
  title = {{The maximum spectral radius of connected graphs with prescribed order and size}},
  author = {Dragan Stevanović},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34905},
  eprint = {2610.34905},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34905},
}
RIS
TY  - UNPB
TI  - The maximum spectral radius of connected graphs with prescribed order and size
AU  - Dragan Stevanović
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.34905
UR  - https://arxiv.org/abs/2610.34905
AB  - In 1986, Brualdi and Solheid asked which connected graph of prescribed order and size has maximum adjacency spectral radius. We complete the classification for every feasible pair of parameters. We prove that no graph outside the dense and star threshold families is extremal, including at ties, and settle the range n≤ e+1, where the star candidate is not defined. The final comparison \emph{between} the dense and star candidates is supplied by Damnjanović's Propositions~4.1--4.2, not reproved here. We combine an exact Bellman recursion with dense-core domination, fractional complete-split bounds, and a virtual-star inequality. Three remaining comparison families (J), (K1), and (K2) are established analytically and by exact polynomial and Sturm certificates. The exact certificates are implemented in Python/SymPy and SageMath.
ER  -