$\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\geqslant 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\geqslant 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)$.