$\sigma$-Irregularity of Trees with Prescribed Maximum Degree: A Majorization--Duality--Stability Framework

Abstract

Trees of maximum $\sigma$-irregularity subject to a prescribed maximum degree $\Delta$ have been characterized for $\Delta =4$ and $\Delta =5$, with the extension to arbitrary $\Delta ⩾3$. This paper develops a unified framework for this class of problems built on three pillars. A majorization-theoretic reformulation that decomposes $\sigma$-extremization into a Schur-convex optimization over degree sequences and a rearrangement type optimization over tree realizations, valid for every $\Delta ⩾3$. We establish a duality between the maximization and minimization problems, alongside the general $\Delta$ closed form for ${\sigma }_{\max }(n,\Delta )$. A stability result showing that the optimality gap between extremal and near extremal trees is bounded independently of $n$ and grows as $\Theta ({\Delta }^3)$.

arXiv comment22 pages, 3 figures