Further results on the lower bound on reduced Zagreb index of trees

This paper extends and corrects previous lower bound results for the general reduced second Zagreb index of trees with a given number of vertices and maximum degree, while also determining the minimum values and characterizing extremal trees for molecular trees with maximum degrees 3 and 4 when $\lambda = -2$.

The Gist

Imagine you are an architect designing a city made entirely of trees. But these aren't just any trees; they are mathematical "molecular trees" used by chemists to understand how real molecules behave.

In this paper, the authors (Milan Bašić and Aleksandar Ilić) are playing a game of "Optimal Design." Their goal is to find the specific shape of a tree that minimizes a very specific score called the General Reduced Second Zagreb Index (let's call it the "Zagreb Score").

Here is the breakdown of their work in simple terms:

1. The Scoreboard: What is the Zagreb Score?

Think of every intersection in your tree-city as a vertex and every road connecting them as an edge.

• Degree: The "degree" of a vertex is simply how many roads connect to it. A leaf on a tree has a degree of 1 (one road). A busy hub might have a degree of 3 or 4.
• The Formula: The Zagreb Score is calculated by looking at every road. For each road connecting two points, you take the "degree" of both points, add a secret number (called $\lambda$) to them, multiply them together, and add up the results for the whole tree.

The authors are trying to find: "What is the absolute lowest possible score a tree can get, and what does that tree look like?"

2. The Two Main Challenges

The paper tackles two different scenarios based on the value of that secret number, $\lambda$.

Scenario A: The "Standard" Case ($\lambda \ge -1$)

Imagine $\lambda$ is a penalty or a bonus added to every intersection.

• The Problem: Previous researchers tried to find the best tree shape for this scenario but missed a few details. They got the answer mostly right, but the "tie-breakers" (the exact conditions for when two trees have the same score) were fuzzy.
• The Fix: The authors cleaned up the math. They proved that for most values of $\lambda$, the best tree looks like a Spider.
  • The Analogy: Imagine a spider with a central body and many long legs. Most legs are short, but maybe one leg is very long. This "Spider Tree" is the most efficient shape to keep the score low.
• The Correction: They specifically fixed a mistake regarding the case where $\lambda = -1$. They showed that sometimes, instead of a perfect spider, the best shape is a Broom (a long handle with bristles on one end, or bristles on both ends). They mapped out exactly when the tree should look like a spider and when it should look like a broom.

Scenario B: The "Chemical" Case ($\lambda = -2$)

This is the tricky part. In chemistry, molecules often have a maximum of 3 or 4 connections per atom. The authors focused on trees where no point connects to more than 3 or 4 other points (Molecular Trees).

• The Goal: Find the tree shape that gives the lowest score when $\lambda = -2$.
• The Method: They used two different "tools" to solve this:
  1. The "Lego" Method (Induction): They started with small trees and showed that if you have a big tree, you can always break it down into a smaller tree without changing the score too much. By peeling away layers like an onion, they proved that the best trees must have a very specific, repetitive structure.
  2. The "Accounting" Method (Algebra): They treated the tree like a balance sheet. They wrote down equations for the number of leaves, hubs, and roads. By solving the math, they found the exact "recipe" for the perfect tree.

3. The Results: What Do the Best Trees Look Like?

For the chemical case ($\lambda = -2$), the authors found that the "winning" trees aren't random. They have a very rigid, repeating pattern:

• For Max Degree 3: The best trees look like a long central path (a backbone) with little "branches" sticking out in a very specific rhythm. It's like a caterpillar where every second segment has a specific number of legs attached.
• For Max Degree 4: The pattern is similar but denser. The best trees look like a central spine where every second point has two little branches attached.

They even categorized these trees by how many vertices (points) they have, creating families of trees named $T_{opt}$ (Optimal Trees).

4. Why Does This Matter?

You might ask, "Who cares about a math score for a tree?"

• Real-World Application: Chemists use these indices to predict how a molecule will act. Does it boil at a high temperature? Is it toxic? Is it stable?
• The Connection: The "Zagreb Score" is a shortcut. If you know the shape of the molecule (the tree), you can calculate this score to guess its physical properties without doing expensive lab experiments.
• The Contribution: By finding the lowest possible score and the exact shape that creates it, the authors give chemists a new tool. They can now say, "If you want a molecule with these specific properties, it must look like this spider or this broom."

Summary

Think of this paper as a Goldilocks guide for tree shapes.

• Previous researchers said, "The best tree is roughly like a spider."
• These authors said, "Actually, it's exactly a spider, unless the conditions are exactly this, in which case it's a broom. And if you are building a chemical molecule (max 3 or 4 connections), here is the exact blueprint for the most efficient tree."

They didn't just find the answer; they corrected the map, filled in the missing details, and provided two different ways to prove it, making the field of chemical graph theory more precise.

Technical Summary

1. Problem Statement

The paper investigates the General Reduced Second Zagreb Index ($GRM_\lambda$) for trees. For a graph $G$, this index is defined as:
$$GRM_\lambda(G) = \sum_{uv \in E(G)} (\deg(u) + \lambda)(\deg(v) + \lambda)$$
where $\lambda$ is an arbitrary real number and $\deg(v)$ is the degree of vertex $v$.

The specific objectives of this research are:

1. Correction and Extension: To correct and extend the equality conditions for the minimal value of $GRM_\lambda$ among trees with $n$ vertices and maximum degree $\Delta$, specifically for the range $\lambda \ge -1$. Previous work by Dehgardia et al. (2023) had incomplete characterizations for the edge case $\lambda = -1$.
2. New Parameter Case: To determine the minimum value and characterize the extremal trees for molecular trees (trees with maximum degree $\Delta \le 4$) when $\lambda = -2$, a case relevant to chemical graph theory.

2. Methodology

The authors employ two distinct mathematical approaches to solve the minimization problem:

A. Inductive Graph Transformations

Used primarily for the $\lambda = -2$ case with $\Delta = 3$. The authors define a set of four graph transformations ($T \to T'$) that reduce the order of the tree while analyzing the change in the index value:

• Transformation 1: Merging adjacent degree-2 vertices (preserves the index).
• Transformation 2: Removing a pendant vertex attached to a degree-2 vertex (increases the index by 1).
• Transformation 3: Removing two leaves attached to a degree-3 vertex (preserves the index).
• Transformation 4: Removing a specific subgraph structure involving degree-2 and degree-3 vertices (decreases the index by 1).
  By applying these transformations recursively, the authors reduce any large tree to a base case, proving that the minimum is achieved only by specific structural configurations.

B. Algebraic System of Equations

Used for both $\Delta = 3$ and $\Delta = 4$ cases. The authors utilize the relationships between the number of vertices of degree $i$ ($n_i$) and the number of edges connecting vertices of degree $i$ and $j$ ($m_{i,j}$).

• They establish linear equations based on the Handshaking Lemma and edge counting: $\sum n_i = n$ and $\sum i \cdot n_i = 2(n-1)$.
• They express the $GRM_{-2}$ index as a linear combination of edge counts: $GRM_{-2}(T) = \sum a_{i,j} m_{i,j}$.
• For $\Delta=3$, the index simplifies to $m_{3,3} - m_{1,3}$.
• For $\Delta=4$, the index is expressed in terms of $m_{i,j}$ variables, allowing the authors to minimize the function by setting specific edge counts to zero and solving for the remaining variables.

3. Key Contributions and Results

Part 1: Correction for $\lambda \ge -1$

The paper corrects the characterization of extremal trees for $\lambda \ge -1$ with maximum degree $\Delta$.

• Result: For $n \ge 4$ and $3 \le \Delta \le n-2$, the minimum value is:
  $$GRM_\lambda(T) \ge (n\lambda + 2n - \Delta\lambda - \Delta - 3)(2 + \lambda) + (\Delta - 1)(\Delta + \lambda)(1 + \lambda)$$
• Extremal Structures:
  • For $\lambda > -1$: The unique extremal tree is a Spider $SP(n, \Delta)$ (a tree with at most one leg of length $>1$).
  • For $\lambda = -1$: The extremal trees are either the Spider $SP(n, \Delta)$ or a Broom $BR(n, \Delta, \Delta')$ (a path with pendent vertices attached to both ends). This distinction for $\lambda = -1$ was the specific gap filled by this paper.

Part 2: Molecular Trees with $\Delta = 3$ and $\lambda = -2$

The authors determine the sharp lower bound for $GRM_{-2}$ in trees where the maximum degree is 3.

• Formula: The minimum value is $-(k+2)$, where $n = 3k + r$ ($r \in \{1, 2, 3\}$).
• Extremal Structures: The optimal trees depend on $n \pmod 3$:
  • $n = 3k+1$: Unique tree $T^1_{opt}(k)$ (a path with pendants on even vertices).
  • $n = 3k+2$: Family $T^2_{opt}(k)$ (subdividing an edge in $T^1_{opt}$).
  • $n = 3k+3$: Family $T^3_{opt}(k)$ (further subdivisions or pendant attachments).
• Validation: Both the inductive transformation method and the algebraic method yielded identical results, confirming the structural characterization.

Part 3: Molecular Trees with $\Delta = 4$ and $\lambda = -2$

Using the algebraic approach, the authors extended the results to trees with maximum degree 4.

• Formula: The minimum value depends on $n \pmod 4$:
  • If $n = 4k+1$: Min value is $-(n+3)$.
  • If $n = 4k+2$: Min value is $-(n+2)$.
  • If $n = 4k+3$: Min value is $-(n+1)$.
  • If $n = 4k+4$: Min value is $-n$.
• Extremal Structures: The authors define specific families of trees ($TT^1_{opt}$ through $TT^4_{opt}$) constructed by attaching pendant vertices to a central path or subdividing edges, which achieve these bounds.

4. Significance

• Theoretical Rigor: The paper resolves ambiguities in previous literature regarding the $\lambda = -1$ case, providing a complete classification of extremal trees for general $\lambda \ge -1$.
• Chemical Graph Theory Application: By focusing on $\lambda = -2$ and molecular trees ($\Delta \le 4$), the results are directly applicable to modeling the physicochemical properties of organic compounds (where carbon atoms have a maximum degree of 4). The reduced Zagreb index is a known predictor for properties like boiling points and stability.
• Methodological Advancement: The paper demonstrates the efficacy of combining inductive graph transformations with algebraic optimization to solve extremal problems in topological indices.
• Future Directions: The authors note that while the algebraic method works for $\Delta=3$ and $4$, the complexity grows rapidly for $\Delta \ge 5$, leaving the general case for $\Delta \ge 5$ as an open problem.

In summary, this work provides a definitive characterization of the lower bounds for the general reduced second Zagreb index on trees, correcting previous errors and offering new, precise structural descriptions for molecular graphs.