Theta-Relations Among Degree-Based Tree Indices

This paper establishes sharp bounds and asymptotic equivalences among the Albertson, Sombor, and Sigma indices for trees, demonstrating that the Sombor index serves as an intermediate descriptor linking global degree dispersion and local edge irregularity through precise $\Theta$-relationships.

The Gist

Imagine you are a city planner trying to understand the "personality" of a neighborhood. In the world of mathematics and chemistry, this neighborhood is a tree (a network of points connected by lines, with no loops, like a family tree or a molecule of oil).

The points are vertices (like houses), and the lines are edges (like streets). The "degree" of a house is simply how many streets connect to it. Some houses are busy hubs with 10 streets; others are quiet cul-de-sacs with just 1.

This paper is about three different "report cards" that mathematicians use to measure how uneven or irregular this neighborhood is. The authors, Jasem and Duaa, wanted to know: If we know the score on one report card, can we predict the score on the others?

Here is the breakdown using simple analogies:

1. The Three Report Cards

Think of these three indices as three different ways to measure the "chaos" of the neighborhood:

• The Albertson Index (The "Neighborly Grudge" Meter):
  • What it measures: How much neighbors hate each other.
  • The Analogy: If a mansion (degree 10) is right next to a shack (degree 1), that's a huge difference. The Albertson index adds up all these differences. It cares about local clashes. If you have a big house next to a small house, the "grudge" score goes up.
• The Sigma Index (The "Variance" Meter):
  • What it measures: How spread out the house sizes are across the whole city.
  • The Analogy: This doesn't care who lives next to whom. It just looks at the whole list of house sizes. Are they all the same size (a perfect suburb)? Or is it a mix of mansions and shacks? It measures the global spread. It's like calculating the standard deviation of house sizes.
• The Sombor Index (The "Hybrid" Meter):
  • What it measures: A mix of size and connection. It looks at the two houses connected by a street and calculates a specific "energy" based on their sizes.
  • The Analogy: Imagine a street connecting a mansion and a shack. The Sombor index calculates the "stress" on that street. It's a bit more complex than just subtracting the sizes; it squares them and takes a square root. It captures both the size of the houses and the contrast between them.

2. The Big Discovery: The "Goldilocks" Connection

The main goal of this paper was to see how these three meters relate to each other. The authors found a beautiful, tight relationship, especially for "extremal" trees (the most chaotic or perfectly ordered versions of these networks).

The "Ruler" Analogy:
Imagine you have a very long, flexible ruler (the Sigma Index) that measures the total spread of the city.

• The authors proved that this ruler strictly controls the Sombor Index. You can't have a crazy Sombor score without a crazy Sigma score.
• They found that the Sombor Index is essentially the Sigma Index multiplied by a constant factor. In math-speak, they are asymptotically equivalent.
  • Simple translation: If the "spread" of the city doubles, the "street stress" (Sombor) also roughly doubles. They grow together like twins.

The "Bridge" Analogy:
The Sombor Index acts as a bridge.

• The Albertson Index only looks at the difference between neighbors (local).
• The Sigma Index only looks at the list of sizes (global).
• The Sombor Index sits in the middle. It captures the "energy" of the connection. The paper shows that in the most extreme cases (like a star-shaped tree where one giant hub connects to many tiny leaves), the Sombor score is directly proportional to the Albertson score.

3. Why Does This Matter? (The Real-World Application)

Why should a regular person care about tree math?

Chemistry and Medicine:
Chemists use these trees to model molecules (like alkanes, which are the basis of fuels and plastics).

• Vertices = Atoms.
• Edges = Chemical bonds.
• Degrees = How many bonds an atom has.

Scientists use these "report cards" to predict how a chemical will behave (e.g., will it boil at a high temperature? Is it toxic?).

• The Sombor Index has been a superstar recently for predicting these properties.
• However, calculating it can be tricky.
• The Paper's Gift: Because the authors proved that Sombor is tightly linked to the simpler Sigma and Albertson indices, chemists can now estimate the complex Sombor score using the simpler, easier-to-calculate scores. It's like being able to guess the price of a luxury car just by knowing the price of its tires and engine, because the math says they always move together.

Summary in One Sentence

This paper proves that in the chaotic world of tree-like networks, the "stress" on the connections (Sombor) is strictly controlled by the overall "spread" of sizes (Sigma) and the "local clashes" between neighbors (Albertson), allowing scientists to predict complex chemical behaviors using simpler math.

Technical Summary

Here is a detailed technical summary of the paper "Theta-Relations Among Degree-Based Tree Indices" by Jasem Hamoud and Duaa Abdullah.

1. Problem Statement

The paper addresses the lack of rigorous structural relationships between three fundamental degree-based topological indices used in chemical graph theory and structural analysis:

• The Albertson Index ($irr(G)$): Measures local edge irregularity based on the absolute difference of degrees of adjacent vertices.
• The Sigma Index ($\sigma(G)$): Measures global vertex degree dispersion (variance) based on the squared difference of degrees.
• The Sombor Index ($SO(G)$): A relatively new index measuring edge-based degree interaction using the Euclidean norm of adjacent vertex degrees ($\sqrt{d_u^2 + d_v^2}$).

While these indices are studied individually, their asymptotic growth rates and interdependencies, particularly within the class of trees (acyclic graphs representing molecular structures like alkanes), were not thoroughly examined. The authors aim to establish sharp two-sided bounds and $\Theta$-relations (asymptotic equivalence up to constant factors) connecting these indices, specifically investigating how global degree dispersion controls edge-based interactions.

2. Methodology

The authors employ a combination of extremal graph theory, algebraic inequalities, and inductive proofs to derive their results:

• Extremal Tree Construction: The study focuses on the family of trees $T_{n, \Delta}$ (trees of order $n$ with maximum degree $\Delta$). They construct specific extremal trees with fixed degree sequences to test bounds.
• Inductive Proofs: The paper utilizes induction on the number of vertices ($n$) to establish bounds for the Sigma and Sombor indices. This involves analyzing the transformation of a tree $T$ to $T'$ by adding or removing pendant vertices and observing the changes in indices.
• Inequality Derivation: The authors apply elementary norm inequalities (e.g., relating Euclidean norms to $L_1$ norms) and properties of convex functions (concavity of the square root) to bound the Sombor index terms ($\sqrt{d_u^2 + d_v^2}$) using linear combinations of degrees and degree differences.
• Degree Sequence Analysis: They analyze trees with specific degree sequences (e.g., sequences dominated by high-degree vertices) to determine when equality holds in their derived bounds.

3. Key Contributions and Results

A. Bounds Relating Sombor and Sigma Indices

The paper establishes that the Sombor index is tightly controlled by the Sigma index (quadratic degree deviation).

• Theorem 3.6: For any tree $T$ of order $n$, the authors derive the following sharp two-sided bound:
  $$\frac{1}{\sqrt{2}} \left( \sigma(T) + \frac{4m^2}{n} \right) \leq SO(T) \leq \sigma(T) + \frac{4m^2}{n}$$
  (Note: $m = n-1$ for trees).
• Asymptotic Equivalence: This result proves that $SO(T) = \Theta(\sigma(T))$. The Sombor index grows at the same asymptotic rate as the variance-type degree structure of the tree.

B. Bounds Relating Sombor and Albertson Indices

The authors investigate the relationship between the Sombor index and the Albertson index, particularly for extremal trees.

• Theorem 3.7: They establish that for extremal trees:
  $$irr(T) \leq SO(T) \leq \sqrt{2} \cdot irr(T) + \sum_{v \in V(T)} d(v)^2$$
• $\Theta$-Relation: The paper demonstrates that for extremal configurations with fixed degree sequences, $SO(T) = \Theta(irr(T))$. This implies that in optimized tree structures, quadratic degree interactions (Sombor) and absolute degree disparities (Albertson) scale proportionally.

C. Structural Characterization

• Intermediary Descriptor: The Sombor index is characterized as an "intermediate descriptor." It bridges the gap between vertex-based irregularity (Sigma) and edge-based irregularity (Albertson).
• Extremal Trees: The paper identifies that trees maximizing the Sigma index (e.g., Star graphs $S_n$) also tend to maximize the Sombor and Albertson indices, confirming that global degree dispersion drives edge-level irregularity.

D. Specific Propositions

• Proposition 3.1: Provides bounds for the Sigma index in terms of parameters $\mu$ and $\eta$ derived from the degree sequence.
• Lemma 3.1: Derives an explicit formula for the Sombor index of a specific extremal tree structure involving degrees $\mu+2$, $\mu+1$, and $1$.

4. Significance and Implications

• Chemical Graph Theory: In the context of modeling acyclic molecules (like alkanes), these findings allow researchers to estimate the Sombor index (which has high predictive power for physicochemical properties) using the simpler, variance-based Sigma index or the Albertson index. This offers a computationally efficient tool for screening large chemical libraries.
• Theoretical Unification: The work unifies three distinct measures of graph irregularity (variance, absolute difference, and Euclidean interaction) under a single analytical framework. It clarifies that vertex-based dispersion fundamentally governs edge-based interactions in trees.
• Predictive Modeling: By establishing that $SO(T)$ and $irr(T)$ are asymptotically equivalent in extremal cases, the paper suggests that structure-property models (QSPR/QSAR) using these indices are robust and interchangeable under specific structural constraints.
• Future Directions: The authors propose extending these relationships to unicyclic and polycyclic graphs and exploring weighted Sombor-type indices.

Conclusion

The paper successfully proves that the Sombor index is not an isolated metric but is mathematically bounded by and asymptotically equivalent to both the Sigma and Albertson indices within the class of trees. This provides a rigorous theoretical foundation for using these indices interchangeably in structural analysis and molecular descriptor estimation, highlighting the Sombor index's role as a comprehensive measure of both global degree dispersion and local edge irregularity.