The maximum spectral radius of connected graphs with prescribed order and size
Dragan Stevanović
Source 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 , 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.