EXTREMAL ALBERTSON IRREGULARITY: THE QUASI-PERFECT GRAPH CONJECTURE, FIBONACCI MULTIPLICITY AND STRUCTURAL STABILITY
Let G be a connected graph whose degree set is {1, . . . , ∆}. We prove the conjectureof Dorjsembe, Buyantogtokh, Gutman, Horoldagva and Réti: the unique graph of order nmaximizing Albertson irregularity in this class is the quasi-perfect graph QPn. The theoremholds without a maximum-degree restriction. We determine the second distinct maximumfor every n ≥ 4 and the third for n ≥ 25, with the remaining orders covered by exact finitecertificates. Second-maximizing graphs have Fibonacci multiplicity outside five exceptionalisomorphism classes. We also give a binary-matrix recurrence for third-maximizer multiplicityand prove a linear-deficit stability theorem. Complete integer-arithmetic verification code isincluded.
Authors
- Tony Newton (ORCID: https://orcid.org/0009-0009-9189-6431)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24397486
- Primary Topic
- Graph theory and applications
- Type
- preprint