Source-linked AI summary
A general algebraic characterization of extremal $\Delta$-trees and $k$-cyclic graphs for degree-homogeneous VDB indices
Milan Bašić
TL;DR
Characterizing maximum-index trees with a prescribed maximum degree is difficult across all congruence classes, since existing bounds and index-specific approaches leave gaps. The paper uses an algebraic penalty-function method to characterize extremal trees for several indices, with an extension to connected k-cyclic graphs. It identifies exact degree ranges for AG and DSO and the same extremal edge-multiplicity structure for qualifying k-cyclic graphs.
Problem
With a prescribed maximum degree, extremal-tree structure varies across congruence classes, while existing upper bounds or index-by-index studies do not provide a unified characterization across them.
Source: §1 · pp. 2–3Method
The method eliminates basic edge multiplicities through edge-sum and degree-sum identities and minimizes a discrete penalty sum governed by five conditions on the weight function.
Source: §1 · p. 3Results
AG satisfies the five conditions exactly for 3 ≤ Δ ≤ 8, and DSO exactly for 3 ≤ Δ ≤ 4; DRSO, SDD, and HSO satisfy them for all Δ ≥ 3.
Source: §1 · p. 3Takeaways & Limitations
For connected k-cyclic graphs with a realizable internal subgraph, the listed indices retain the extremal edge-multiplicity structure from the tree characterization.
Source: §3 · p. 15The k-cyclic construction applies when n is sufficiently large relative to k and Δ to guarantee a simple connected internal subgraph.
Source: §3 · p. 15
Abstract
from arXiv · showhide
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 $\Delta \ge 3$. By expressing the edge multiplicities of the basis $\mathcal{B} = \{(1,\Delta), (\Delta,\Delta)\}$ 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{\Delta - 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 $\Delta$-trees for the Degree-Ratio Sombor ($DRSO$), Symmetric Division Deg ($SDD$), and Hyperbolic Sombor ($HSO$) indices for all $\Delta \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 \Delta \le 8$, and $DSO$ if and only if $3 \le \Delta \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.
1. Introduction
The paper addresses the gap between upper bounds that are tight in only one congruence class and index-by-index characterizations that often require separate proofs. It develops a shared algebraic method for characterizing extremal trees and applies it to several degree-homogeneous VDB indices.
1. Introduction
- Degree-bounded trees split into Δ−1 congruence classes of n (mod Δ−1), unlike the unconstrained setting where the star typically maximizes these indices.A VDB index sums a symmetric weight of endpoint degrees over graph edges.Source: §1 · pp. 1–2
- The decomposition targets a gap: basic-edge-only upper bounds are realizable in only one congruence class, leaving other classes unresolved.Prior complete characterizations were generally pursued one index at a time, often for molecular trees.Source: §1 · p. 2
- The method eliminates basic edge multiplicities using edge-sum and degree-sum identities, then minimizes a discrete penalty sum over non-basic edges.Five conditions on the weight function determine the penalty hierarchy and the extremal tree family across all congruence classes of n (mod Δ−1).Source: §1 · p. 3
- The framework gives complete extremal-tree characterizations for DRSO, SDD, and HSO for every Δ ≥ 3.These characterizations include molecular trees with Δ ≤ 4.Source: §1 · p. 3
- AG satisfies the five conditions exactly for 3 ≤ Δ ≤ 8, while DSO satisfies them exactly for 3 ≤ Δ ≤ 4.The paper says this identifies why the extremal topology changes for Δ ≥ 5 for DSO.Source: §1 · p. 3
- The approach extends to connected k-cyclic graphs because changing the edge count shifts the constant term but leaves the penalty coefficients unchanged.The paper carries out the derivation and tree construction for k = 0, then presents the direct extension for k ≥ 1.Source: §1 · p. 3
2. Algebraic Decomposition Relative to the Basis B = {(1, ∆), (∆, ∆)}
This section develops a maximum-index framework that rewrites the VDB index as a constant minus penalties on non-basic edge types and uses conditions on the weight function to characterize extremal trees. It applies the framework to several indices, identifies degree ranges for DSO and AG, and describes extremal families across congruence classes of n modulo Δ−1.
2. Algebraic Decomposition Relative to the Basis B = {(1, ∆), (∆, ∆)}
- Maximizing TI(T) reduces to minimizing the summed penalty G(i,j) over non-basic edge multiplicities; the basis-edge counts are expressed through degree-sum identities.The decomposition separates a term depending on n and ∆ from the non-basic penalty sum.Source: §2 · pp. 3–4
2.1. Properties of the Weight Function
- Under properties (P1)–(P5), the penalty bounds make G(x,∆) positive and larger penalties apply to non-basic edges than the boundary edge type (x,∆).In particular, G(x,j) > G(x,∆), G(x,x) > 2G(x,∆), and G(i,x) > G(x,∆) for the stated degree ranges.Source: §2.1 · p. 5
- For weights satisfying (P1)–(P5), extremal trees use only basis edges when n ≡ 2 (mod ∆−1); otherwise they have one internal vertex of degree x with n ≡ x + 1 (mod ∆−1).In the latter case, the tree has m_x,∆ = x, with x the unique integer in {2,…,∆−1} satisfying the congruence.Source: §2.1 · p. 6
2.2. Applications to Degree-Homogeneous Topological Indices
- The DRSO, SDD, and HSO indices have extremal trees characterized by Theorem 1 for every ∆ ≥ 3.The corollaries state unique characterization for DRSO and HSO and characterization for SDD.Source: §2.2 · pp. 7–9
- For the AG index, Theorem 1 characterizes extremal trees exactly for 3 ≤ ∆ ≤ 8; conditions (P4) and (P5) fail for ∆ ≥ 9.The two conditions hold through ∆ = 8 and fail from ∆ = 9 onward.Source: §2.2 · pp. 9–10
- For DSO, the basis {(1,∆),(∆,∆)} applies to molecular trees with ∆ ≤ 4, while condition (P5) fails for ∆ ≥ 5.Source: §2.2 · p. 10
- For the DSO index, Theorem 1 uniquely characterizes the extremal trees exactly for 3 ≤ Δ ≤ 4.The required properties (P1)–(P5) hold simultaneously if and only if Δ ≤ 4.Source: §2.2 · pp. 10–11
- Property (P5) fails for every Δ ≥ 5 because R(1, Δ) < R(2, Δ), but holds for Δ = 3 and Δ = 4.For Δ = 3, R(1,3) ≈ 0.125 exceeds R(2,3) ≈ 0.084; for Δ = 4, R(1,4) ≈ 0.156 exceeds both R(2,4) ≈ 0.153 and R(3,4) ≈ 0.086.Source: §2.2 · p. 11
- Property (P4) also holds for Δ = 3 and Δ = 4, with the respective supremum bounds below C3 ≈ 0.125 and C4 ≈ 0.156.For Δ = 3, sup H(t,2) < 0.10; for Δ = 4, the bounds are below 0.10 for x = 2 and below 0.15 for x = 3.Source: §2.2 · p. 11
2.3. Explicit Maximum Values and Constructive Realization of Extremal Trees
- Across n ≡ x+1 (mod Δ−1), x ∈ {2, …, Δ}, the optimal edge multiplicities determine the degree counts and an explicit maximum value of TI(T).For x < Δ, the non-basic edge type (x, Δ) has multiplicity x and exactly one vertex has degree x; x = Δ subsumes the case with no non-basic edges.Source: §2.3 · p. 12
- The extremal family is constructed from an internal tree H by attaching leaves to raise its vertices to degree Δ, except for one selected degree-x vertex when x < Δ.The construction defines Topt(n, Δ), and every tree satisfying Theorem 1 is generated by it, confirming the unique extremal family.Source: §2.3 · pp. 12–13
3. Concluding Remarks and Extension to Graphs of Prescribed Order and Size (k-Cyclic Graphs)
The paper’s five analytical conditions characterize extremal trees for several VDB indices and identify degree thresholds for AG and DSO. The decomposition extends to connected k-cyclic graphs, where the penalty function remains unchanged and the tree edge-multiplicity structure applies under a realization condition.
3. Concluding Remarks and Extension to Graphs of Prescribed Order and Size (k-Cyclic Graphs)
- The five analytical conditions characterize extremal Δ-trees across all Δ−1 congruence classes for DRSO, SDD, and HSO, and give thresholds Δ≤8 for AG and Δ≤4 for DSO.The conditions are also presented as an analytical test for diagonal-constant VDB invariants.Source: §3 · p. 14
- Changing from trees to connected graphs with m=n−1+k changes only the constant terms; coefficients of non-basic edge multiplicities and the discrete penalty function remain unchanged.The generalized constant is denoted C_k(n,Δ), while G(x,y) is identical to the tree penalty function.Source: §3 · pp. 14–15
- For fixed cyclomatic number k, the earlier lemma and validity domains carry over without modification, while the degree-sum congruence is adjusted for k.Source: §3 · p. 15
- For sufficiently large n to realize the required internal subgraph, extremal k-cyclic graphs retain the tree edge-multiplicity structure for DRSO, SDD, HSO, AG, and DSO within their stated degree ranges.The ranges are Δ≥3 for DRSO, SDD, and HSO; 3≤Δ≤8 for AG; and 3≤Δ≤4 for DSO.Source: §3 · p. 15
- Minimal order thresholds for simple k-cyclic realizations and transitions to alternative bases when the AG or DSO conditions fail remain open directions.The stated failure ranges are Δ≥9 for AG and Δ≥5 for DSO.Source: §3 · p. 15