A general algebraic characterization of extremal Δ-trees and k-cyclic graphs for degree-homogeneous VDB indices
Abstract
We present a general algebraic method for maximizing a vertex-degree-based (VDB) topological index TI(G) = ∑uv ∈ E(G) f(d(u),d(v)) over the class of n-vertex trees with a prescribed maximum degree Δ≥ 3. By expressing the edge multiplicities of the basis ℬ = {(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 Δ≥ 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 ≤ Δ≤ 8, and DSO if and only if 3 ≤ Δ≤ 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.
Related
- A general theorem in spectral extremal graph theory
- Surfaces of general type with extremal cotangent dimension
- Algebraic hyperbolicity of very general hypersurfaces in projective spaces
- Birational Automorphism Bounds for General-Type Foliations on Surfaces via Pluricanonical Indices
- Reference-State Bootstrap Correction and Kernel Characterization of Residual-Based Fit Indices in Structural Equation Models
BibTeX
@misc{basic2026general,
title = {{A general algebraic characterization of extremal $Δ$-trees and $k$-cyclic graphs for degree-homogeneous VDB indices}},
author = {Milan Bašić},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34361},
eprint = {2610.34361},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34361},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A general algebraic characterization of extremal Δ-trees and k-cyclic graphs for degree-homogeneous VDB indices
AU - Milan Bašić
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34361
UR - https://arxiv.org/abs/2610.34361
AB - We present a general algebraic method for maximizing a vertex-degree-based (VDB) topological index TI(G) = ∑_uv ∈ E(G) f(d(u),d(v)) over the class of n-vertex trees with a prescribed maximum degree Δ≥ 3. By expressing the edge multiplicities of the basis ℬ = {(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 Δ≥ 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 ≤ Δ≤ 8, and DSO if and only if 3 ≤ Δ≤ 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.
ER -