A general algebraic characterization of extremal $Δ$-trees and $k$-cyclic graphs for degree-homogeneous VDB indices

Source abstract

We present a general algebraic method for maximizing a vertex-degree-based (VDB) topological index $TI(G) = \sum_{uv \in E(G)} f(d(u),d(v))$ over the class of $n$-vertex trees with a prescribed maximum degree $Δ\ge 3$. By expressing the edge multiplicities of the basis $\mathcal{B} = \{(1,Δ), (Δ,Δ)\}$ via degree-sum identities, we reduce the maximization of $TI(T)$ to the minimization of an explicit discrete penalty function $G(x,y)$ over the non-basic edges. We formulate five analytical conditions on the weight function $f(x,y)$ that dictate the optimal edge distributions, yielding a complete characterization of the extremal trees across all congruence classes of $n \pmod{Δ- 1}$. Additionally, we provide their explicit construction by attaching leaves to a core of internal vertices. Applying this framework, we obtain the complete characterization of extremal $Δ$-trees for the Degree-Ratio Sombor ($DRSO$), Symmetric Division Deg ($SDD$), and Hyperbolic Sombor ($HSO$) indices for all $Δ\ge 3$. Furthermore, the analytical conditions identify the exact degree thresholds for the Arithmetic-Geometric ($AG$) and Diminished Sombor ($DSO$) indices, showing that the same extremal family maximizes $AG$ if and only if $3 \le Δ\le 8$, and $DSO$ if and only if $3 \le Δ\le 4$. Finally, since changing the edge count from $m = n - 1$ to $m = n - 1 + k$ affects only the constant term in the decomposition while leaving the penalty function $G(x,y)$ invariant, the method extends directly to connected $k$-cyclic graphs.