A Unified Linear Programming Approach for Maximizing Vertex-Degree-Based Indices of Trees
Abstract
The problem of maximizing vertex-degree-based topological indices over trees with a prescribed order and maximum degree Δ has traditionally relied on ad-hoc combinatorial arguments. In this paper, we establish a unified linear programming approach that systematically resolves these extremal problems. By formulating the optimization over degree-pair multiplicities, the search for an extremal tree reduces to minimizing a discrete dual penalty. Treating vertex degrees as continuous variables yields an analytical single-variable test condition that guarantees global optimality. We apply this framework across a diverse collection of invariants. We prove that the standard basic feasible solution is optimal for the Tangent Sombor, SO1, SO2, Albertson, and σ-irregularity indices for all Δ≥ 3. However, the dual optimality conditions establish exact analytical thresholds at which the standard basis loses optimality, necessitating a transition to alternative basic feasible solutions. For the Arithmetic-Geometric (AG) index, the standard basis is optimal strictly for Δ≥ 9; for smaller maximum degrees (3 ≤ Δ≤ 8), optimization shifts to an alternative edge basis, allowing us to explicitly construct and characterize all extremal trees across congruence classes, including chemical trees (Δ∈ {3, 4}). Conversely, for the Triangle Volume index (SO11), the standard basis is optimal exclusively for Δ≤ 8, while for Δ≥ 9 we analytically derive a novel, degree-dependent optimal basis to explicitly construct its extremal configurations.
Related
- Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
- Maximizing the magnitude of Strictly Standardized Mean Difference of a Linear Combination
- Mathematical Programming in Machine Learning and Artificial Intelligence: A Unified Taxonomy of Models and Applications
- PDLP: a practical first-order method for large-scale linear programming
- Linear circumference in vertex-transitive graphs
BibTeX
@misc{basic2026unified,
title = {{A Unified Linear Programming Approach for Maximizing Vertex-Degree-Based Indices of Trees}},
author = {Milan Bašić},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20364},
eprint = {2610.20364},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20364},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Unified Linear Programming Approach for Maximizing Vertex-Degree-Based Indices of Trees
AU - Milan Bašić
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20364
UR - https://arxiv.org/abs/2610.20364
AB - The problem of maximizing vertex-degree-based topological indices over trees with a prescribed order and maximum degree Δ has traditionally relied on ad-hoc combinatorial arguments. In this paper, we establish a unified linear programming approach that systematically resolves these extremal problems. By formulating the optimization over degree-pair multiplicities, the search for an extremal tree reduces to minimizing a discrete dual penalty. Treating vertex degrees as continuous variables yields an analytical single-variable test condition that guarantees global optimality. We apply this framework across a diverse collection of invariants. We prove that the standard basic feasible solution is optimal for the Tangent Sombor, SO_1, SO_2, Albertson, and σ-irregularity indices for all Δ≥ 3. However, the dual optimality conditions establish exact analytical thresholds at which the standard basis loses optimality, necessitating a transition to alternative basic feasible solutions. For the Arithmetic-Geometric (AG) index, the standard basis is optimal strictly for Δ≥ 9; for smaller maximum degrees (3 ≤ Δ≤ 8), optimization shifts to an alternative edge basis, allowing us to explicitly construct and characterize all extremal trees across congruence classes, including chemical trees (Δ∈ {3, 4}). Conversely, for the Triangle Volume index (SO_11), the standard basis is optimal exclusively for Δ≤ 8, while for Δ≥ 9 we analytically derive a novel, degree-dependent optimal basis to explicitly construct its extremal configurations.
ER -