On the maximum σ-irregularity of trees with given order and maximum degree

The σ -irregularity index of a graph is defined as the sum of squared degree differences over all edges and provides a sensitive measure of structural heterogeneity. In this paper, we study the problem of maximizing σ ( T ) among all trees of fixed order n and prescribed maximum degree Δ ≥ 4 . By expressing the problem in terms of edge–degree multiplicities, we derive a linear programming formulation and analyze its dual. This approach yields sharp upper bounds for σ ( T ) and leads to a detailed description of extremal degree–pair distributions. We show that the extremal problem can be completely resolved for the congruence classes n ≡ 1 ( mod Δ ) and n ≡ 0 ( mod Δ ) . When n ≡ 1 ( mod Δ ) , the linear program admits an integral optimal solution, and the bound for σ ( T ) is tight. When n ≡ 0 ( mod Δ ) , the linear relaxation is not attainable by any tree; nevertheless, by introducing a penalty function derived from dual slack variables, we determine the exact maximum value of σ ( T ) . In both cases, all extremal trees are characterized explicitly and consist exclusively of vertices of degrees 1, 2, and Δ , with edges incident to Δ -vertices playing a dominant role.