Algebraic method finds optimal trees for graph degree indices
A general algebraic characterization of extremal $Δ$-trees and $k$-cyclic graphs for degree-homogeneous VDB indices
Discrete Mathematics
Summary
Some scientists worked on a way to pick the best kinds of tree-shaped networks that have limits on how connected each point can be. They found a math trick to figure out which arrangements of connections make certain scores based on the points’ degrees as big as possible. Their method also helps with networks that have a few more connections than trees. They showed how this works for different scoring formulas that measure how connected the network is in special ways.
What this means in practice
- •For network designers: Design networks with prescribed maximum node connections to maximize connectivity-based quality measures relevant for communication or infrastructure.
- •For chemical informatics teams: Construct molecular graphs that optimize degree-based molecular descriptors used in predicting chemical properties or behaviors.
Authors
Milan Bašić
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.