Institute of Mathematics

Abstract:  The Sombor-index-like invariant $SO_6$ has recently attracted considerable attention in extremal graph theory. In particular, among several open problems formulated in Z. Tang, Q. Li, H. Deng (2023), the authors proposed determining the maximum value of $SO_6$ over all trees with prescribed order $n$ and maximum degree $\Delta$. This problem has been settled for chemical trees (i.e., $\Delta\in\{3,4\}$), but remains open for general $\Delta\ge5$. We settle the problem in two congruence classes $n\equiv1 \pmod{\Delta}$ and $n\equiv0 \pmod{\Delta}$ for every $\Delta\ge5$. Using a linear programming formulation over degree pair multiplicities, we derive a sharp upper bound on $SO_6$ that is attained whenever $n\equiv1 \pmod{\Delta}$. In this case, the extremal value is achieved by a unique degree pair distribution, and all extremal trees are characterized explicitly. When $n\equiv0 \pmod{\Delta}$, the optimal solution of the linear relaxation is not realizable by any tree. To overcome this difficulty, we introduce a penalty function induced by dual slack variables and use it to determine the exact maximum value in this case as well. Thus, for both congruence classes considered, the extremal problem is solved exactly and all extremal trees are fully described.