# On Gutman Index of Extremal Trees

Jasem Hamoud

► To cite this version:

Jasem Hamoud. On Gutman Index of Extremal Trees. 2025. hal-05403292

HAL Id: hal-05403292

https://hal.science/hal-05403292v1

Preprint submitted on 8 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# ON GUTMAN INDEX OF EXTREMAL TREES

## JASEM HAMOUD

**ABSTRACT.** In this paper, we investigate the Gutman index Gut(G) of a graph G where it defined by Gut(G) = $\sum_{\{u,v\} \subseteq V(G)} d_G(u) d_G(v) \text{dist}(u, v)$. This study investigates the Gutman index specifically for classes of trees, focusing on caterpillar trees and (1, i)-trees. We derive closed-form expressions that represent the Gutman index as weighted Wiener-type sums involving internal and pendent vertices. Within caterpillar trees having fixed degree sequences, we identify configurations that minimize and maximize the Gutman index, thereby determining optimal vertex distributions along the spine. Also, we formulate explicit novelty formula for the Zagreb indices and other distance-based indices for caterpillars extended by uniform pendant vertex layers. These findings provide new structural insights into distance-degree based indices relevant in chemical graph theory.

**Keywords:** Gutman index, Caterpillar trees, Degree sequence, Path, Zagreb index.

**MSC 2020:** 05C05, 05C12, 05C20, 05C25, 05C35, 05C76, 52C20, 68R10.

## 1. INTRODUCTION

Let $G = (E, V)$ be a simple graph with vertex set $V = V(G) = \{v_1, v_2, \dots, v_n\}$ and edge set $E = E(G) = \{e_1, e_2, \dots, e_m\}$. A *path* in the graph $G$ is a sequence of vertices such that each consecutive pair of vertices in the sequence is connected by an edge, and, no vertex appears more than once.

Let $T$ be a tree containing a path of size $\ell$ with vertices $v_1, v_2, \dots, v_\ell$. Let for $i = 1, 2, \dots, \ell, m_i$ monovalent vertices be attached to vertex $v_1$. Such a tree is referred to as a *caterpillar* [6], and will be denoted by $T_\ell(m_1, m_2, \dots, m_\ell)$.

An *extremal tree*, with respect to a graph invariant $I$, is a tree that attains the absolute extremum (maximum or minimum) of $I$ among all trees within a specified class. Such classes may include, for example, all trees on $n$ vertices, all trees with a given degree sequence, or all caterpillar trees with a specified degree sequence.

The *degree* of a vertex $w$ in $G$, denoted by $d_G(w)$, is the number of vertices adjacent to $w$. The length of the shortest path between vertices $u$ and $v$ of the graph $G$ is their *distance*, denoted by $\text{dist}(u, v)$. The sum of distances between all pairs of vertices of the graph $G$ is called the *Wiener index*

$$ (1) \qquad W(G) = \sum_{\{u,v\} \subseteq V(G)} \text{dist}(u, v). $$

It was first introduced in 1947, by Wiener [25], and eventually much studied [14, 24, 17, 23]. The *degree distance* is an important topological index that combines information about the degrees of vertices and the distances between them in a graph. It is defined [18] as

$$ (2) \qquad \mathbb{D}'(G) = \sum_{\{u,v\} \subseteq V(G)} [d_G(u) + d_G(v)] \text{dist}(u, v). $$

<footnote>The author is grateful to prof. Ivan Gutman and to Dr. Duaa Abdullah for their helpful comments.</footnote>
The degree distance was initially introduced by Dobrynin and Kochetova [5] and has since been studied extensively to establish bounds, exact values for special graph classes, and its relation to other graph invariants. This index has found applications in chemistry, network analysis, and combinatorics, providing insights into graph structure by reflecting both local and global connectivity properties.

The Gutman index Gut is a natural vertex-degree-extension of the Wiener index. It defined as

$$ (3) \qquad \text{Gut}(G) = \sum_{\{u,v\} \subseteq V(G)} d_G(u) d_G(v) \text{ dist}(u, v). $$

This topological index was invented in 1994 by [7] as a refinement of the earlier proposed Schultz index [20]. In this first paper [7], the fundamental relation between Gut and W, Theorem 2.1, was established. Since then, the mathematical properties of Gut were extensively studied, and this topological index found numerous applications in chemistry. For instance, Das [9] identified the trees with fixed order and diameter that maximize and minimize the Gutman index. Subsequently, Andriantiana et al. [1] analyzed the extremal values of the Gutman index among trees constrained by a given degree sequence. Employing a majorization technique, they provided a characterization of these trees possessing maximal Gut-values. For other details of these researches and for an exhaustive bibliography see [8]; see also [10, 4, 16].

The Zagreb indices, initially introduced in [12] and [11] in 1972 and 1974, represent some of the earliest and most extensively investigated degree-based topological indices [22]. For a simple connected graph $G = (V, E)$, these indices are defined as

$$ M_1(G) = \sum_{v \in V} d_G(v)^2, \quad M_2(G) = \sum_{\{u,v\} \in E} d_G(u) \cdot d_G(v). $$

Caterpillars constitute a significant subclass of tree graphs, characterized by the property that the removal of all pendant vertices results in a path. This path is usually referred to as the spine of the underlying caterpillar. The study of structural properties and extremal problems concerning various degree-based topological indices of caterpillars has attracted substantial scholarly interest. For instance, Schmuck et al. [19] derived sharp upper and lower bounds on Gut of caterpillars with a fixed number of vertices and legs. More recently, Shetty et al. [21] determined the maximum and minimum Gut-values among caterpillars possessing a prescribed degree sequence. Their results demonstrate that extremal caterpillars achieving the maximum Gutman index are constructed by positioning the vertices of highest degree as centrally as possible along the spine, whereas those achieving the minimum index exhibit a maximal asymmetry in the placement of high-degree vertices.

Despite considerable advancements in addressing extremal problems pertaining to Gutman index of general trees and caterpillars with fixed order, a comprehensive characterization of the Gutman index of caterpillars subject to arbitrary degree sequence, remained only partially resolved. This gap motivated the present investigation.

## 2. PRELIMINARIES

There exists a remarkably simple relationship between the Wiener and Gutman indices [7]:

**Theorem 2.1.** Let T be a tree on n vertices. Then

$$ (4) \qquad \text{Gut}(T) = 4W(T) - (2n-1)(n-1). $$

Knowing that the star $S_n$ and path $P_n$ are the n-vertex trees with extremal Wiener indices [11], we immediately arrive at:
**Corollary 2.2.** Let $T$ be a tree on $n$ vertices. Then

$$S_n \leq \text{Gut}(T) \leq P_n,$$

with equality if and only if $T \cong S_n$ and $T \cong P_n$, respectively. In addition,

$$\text{Gut}(S_n) = (n-1)(2n-3) \quad \text{and} \quad \text{Gut}(P_n) = \frac{2}{3}(n-1)\left(n^2 - 2n + \frac{3}{2}\right).$$

Let $\mathcal{D} = (d_1, d_2, \dots, d_n)$ be a degree sequence where $d_1 \geq d_2 \geq \dots \geq d_n$. Let $\mathbb{C}(\mathcal{D})$ denote the set of all caterpillar trees with a given degree sequence $\mathcal{D}$. Shetty et al. [21] completely characterized the caterpillars in $\mathbb{C}(\mathcal{D})$ that attain the maximum and minimum Gutman index.

**Lemma 2.3 ([4]).** Let $G$ be a connected graph of order $n$, diameter $d$ and minimum degree $\delta$. Let $v, v'$ be any vertices of $G$. If $d_G(v) \leq n - d(\delta + 1)/3 + 2\delta$ and $d(v, v') \geq 3$. Then,

$$(5) \qquad d_G(v) + d_G(v') \leq n - \frac{1}{3}d(\delta + 1) + 4\delta.$$

Theorem 2.4 considering the extremal caterpillar is characterized by the placement of vertices with the highest degrees as centrally as possible along the spine. More explicitly, denote by $\mathbb{C}_{\max}(\mathcal{D})$ the caterpillar constructed by positioning the non-pendent vertices (those vertices with degree at least 2) in a non-increasing sequence of degrees arranged symmetrically around the spine's center.

**Theorem 2.4 (Maximum Gutman index).** Throughout the class of all caterpillars with $\mathcal{D}$, there exists a unique, up to isomorphism, caterpillar whose Gutman index attains the maximum value. Then, for any caterpillar $\mathbb{C}$ belonging to the family $\mathbb{C}(\mathcal{D})$, one has

$$(6) \qquad \text{Gut}(\mathbb{C}) \leq \text{Gut}(\mathbb{C}_{\max}(\mathcal{D})),$$

with equality holding if and only if $\mathbb{C}$ is isomorphic to $\mathbb{C}_{\max}(\mathcal{D})$.

Among all caterpillars with $\mathcal{D}$, the unique caterpillar (up to isomorphism) that achieves the minimum Gutman index through Theorem 2.5 is characterized by the arrangement wherein the vertices of highest degrees are positioned asymmetrically as possible, that is, clustered consecutively at one extremity of the spine.

**Theorem 2.5 (Minimum Gutman index).** Let $\mathbb{C}_{\min}(\mathcal{D})$ as the caterpillar constructed by ordering the vertices with the largest degrees at one endpoint of the spine in non-increasing order. Then,

$$(7) \qquad \text{Gut}(\mathbb{C}) \geq \text{Gut}(\mathbb{C}_{\min}(\mathcal{D})),$$

with equality holding if and only if $\mathbb{C}$ is isomorphic to $\mathbb{C}_{\min}(\mathcal{D})$.

In particular, case where the degree sequence corresponds to a path (i.e., all degrees satisfy $d_i \leq 2$), the extremal constructions $\mathbb{C}_{\max}(\mathcal{D})$ and $\mathbb{C}_{\min}(\mathcal{D})$ coincide with the unique path realizing this degree sequence. This recovers the well-established result that the Gutman index remains invariant across all paths of fixed length. For example, let $T$ be a tree with degree sequence given by Figure 1 and $n = 48$ vertices

$$\mathcal{D} = (6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 1, 1, \dots, 1). \underbrace{34}_{34}$$

There are 14 vertices of degree $\geq 3$ (pendent vertices). When placed on the spine, they require

$$3(6 - 2) + 4(5 - 2) + 5(4 - 2) + 2(3 - 2) = 12 + 12 + 10 + 2 = 36$$

pendent leaves, but only 34 leaves are available. Hence the spine must contain exactly 2 additional degree-2 vertices, giving a spine of length 16. Thus,

* for $\mathbb{C}_{\min}(\mathcal{D})$: the 14 branch vertices are placed consecutively at one end of the spine, in non-increasing degree order.
* for $C_{max}(\mathcal{D})$: the 14 branch vertices are placed as centrally as possible (positions 2-15 on the 16-vertex spine, symmetric around the centre).

Thus

$$ \begin{cases} C_{max}(\mathcal{D}) = 1122, \\ C_{min}(\mathcal{D}) = 1034. \end{cases} $$

<figure><img src="image_2.png" /><figcaption>FIGURE 1. Extremal caterpillars corresponding to the degree sequence $\mathcal{D} = (6^3, 5^4, 4^5, 3^2, 1^{34})$ are considered. The top configuration the minimal Gutman index of 1034. In the bottom the maximal Gutman index of 1122.</figcaption></figure>

### 3. EXTREMAL PROBLEMS FOR GUTMAN INDEX

In this section, the path graph $P_n$ uniquely minimizes both the first Zagreb index $M_1(P_n) = 4n - 6$ and the second Zagreb index $M_2(P_n) = 4n - 10$. Conversely, the star graph $S_n$ uniquely maximizes the first Zagreb index, yielding $M_1(S_n) = n^2 - 1$. The systematic algorithm 1 is designed for clarity and modularity: it first generates the tree structure, then computes the values required for the Gutman index.

**Algorithm 1** Compute Gutman Index and Visualize Tree.

**Require:** Number of vertices $n$

**Ensure:** Gutman index Gut of generated tree $T$

1. Generate a random tree $T$ with $n$ vertices

2. **for all** vertex $v$ in $T$ **do**

3. Compute degree $d_T(v)$

4. **end for**

5. Initialize Gut $\leftarrow 0$

6. **for all** unordered pairs of distinct vertices $\{u, v\}$ in $T$ **do**

7. Compute shortest path distance $dis(u, v)$ in $T$

8. Update Gut $\leftarrow$ Gut + $d_T(u) \cdot d_T(v) \cdot dis(u, v)$

9. **end for**

10. Arrange $T$ in a hierarchical top-to-bottom layout for visualization

11. Draw tree $T$ with vertex labels and edges according to layout

12. Include Gutman index Gut.

13. **return** Gutman index Gut

In next figure 2, we provide Gutman index of tree $T$ with $n = 8$ and $n = 16$ vertices according to Algorithm 1.
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Gutman index of tree T with $n = 8$ and $n = 16$ vertices.</figcaption></figure>

To demonstrate the concept of the shortest path in trees—including extreme trees—we follow the following algorithm: First, using Algorithm 2, we generate random trees with a given number of vertices.

**Algorithm 2 Generate Random Tree**

**Require:** Integer $n \ge 2$ (number of vertices), Integer $Q$ (number of queries)

1: $E \leftarrow \emptyset$

2: **for** $i = 1$ to $n-1$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;`p` ← `RandomInteger`(0, $i-1$)

4: &nbsp;&nbsp;&nbsp;&nbsp;Add edge (`p`, `i`) to `E`

5: **end for**

Secondly, convert the tree into *Adjacency List* among Algorithm 3 where *Adjacency List* it is a memory-efficient data structure for representing undirected graphs. Consider a graph with $n$ vertices labeled from 0 to $n-1$. To represent this graph, we use an array `adj[0 ... n - 1]`, where: `adj[i] = list of all vertices j such that (i, j) ∈ E`. Because the graph is undirected, each edge `(i, j)` is included in both `adj[i]` and `adj[j]`.

For a tree with $n$ vertices, there are exactly $n-1$ edges, so the total number of entries across all adjacency lists is $2(n-1) = O(n)$. This structure requires much less space than the $O(n^2)$ seen in an $n \times n$ adjacency matrix.

**Algorithm 3 Convert the tree into an Adjacency List.**

1: Initialize `adj[0..n-1]` as empty lists

2: **for** each edge `(u, v) ∈ E` **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;`adj[u].append(v)`, `adj[v].append(u)`

4: **end for**

Thirdly, we fixed visualization for Gutman index among Algorithm 4. Then, we applied Algorithm 1.
**Algorithm 4 Fixed visualization.**

1: Compute node positions pos ← SpringLayout($G$, seed = 42)
2: **for** query = 1 to $Q$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;s ← RandomInteger(0, $n-1$), $t$ ← RandomInteger(0, $n-1$)
4: &nbsp;&nbsp;&nbsp;&nbsp;**while** $t = s$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$t$ ← RandomInteger(0, $n-1$)
6: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
7: &nbsp;&nbsp;&nbsp;&nbsp;Initialize parent[0..$n-1$] ← $-1$, visited[0..$n-1$] ← false
8: &nbsp;&nbsp;&nbsp;&nbsp;queue ← $\emptyset$, enqueue $s$, visited[$s$] ← true
9: &nbsp;&nbsp;&nbsp;&nbsp;**while** queue $\neq \emptyset$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$u$ ← dequeue()
11: &nbsp;&nbsp;&nbsp;&nbsp;**for** each neighbor $v$ of $u$ in adj[$u$] **do**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** not visited[$v$] **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visited[$v$] ← true, parent[$v$] ← $u$
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;enqueue $v$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
16: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
17: **end while**
18: &nbsp;&nbsp;&nbsp;&nbsp;path ← $\emptyset$, current ← $t$
19: &nbsp;&nbsp;&nbsp;&nbsp;**while** current $\neq -1$ **do**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;path.append(current)
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current ← parent(current)
22: &nbsp;&nbsp;&nbsp;&nbsp;**end while**
23: &nbsp;&nbsp;&nbsp;&nbsp;Reverse path
24: **end for**

Regarding the second Zagreb index $M_2$, among trees with $n$ vertices, the maximizing structure is the tree that attains the greatest sum of products of adjacent vertex degrees. This tree is typically a highly branched configuration resembling either a complete binary tree or, for small values of $n$, a “double star.” The maximize or minimize $M_1$ or $M_2$ subject to constraints had discussed among Theorem 3.1 as we will show that.

**Theorem 3.1.** Consider the class $C(\mathcal{D})$ of caterpillar trees characterized by the degree sequence $\mathcal{D}$. Then,

* The second Zagreb index $M_2$ (and, consequently, the Gutman index Gut) attains its maximum value when vertices of high degree are positioned as centrally as possible along the spine of the caterpillar.

* Conversely, the index $M_2$ (and hence Gut) attains its minimum value when vertices of high degree are consecutively grouped at one end of the spine.

**Problem 1.** Given an arbitrary graphical tree with degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ such that $d_1 \ge d_2 \ge \dots \ge d_n$, the sequence $\mathcal{D}$ determines (not necessarily uniquely) the trees $T_{\min}(\mathcal{D})$ and $T_{\max}(\mathcal{D})$ in the set $\mathcal{T}(\mathcal{D})$ which achieve the minimum and maximum values, respectively, of the Gutman index Gut. More precisely, these extremal trees satisfy

$$ \text{Gut}(T_{\min}(\mathcal{D})) = \min_{T \in \mathcal{T}(\mathcal{D})} \text{Gut}(T), \quad \text{Gut}(T_{\max}(\mathcal{D})) = \max_{T \in \mathcal{T}(\mathcal{D})} \text{Gut}(T). $$

Equivalently, Problem 1 holds for the first Zagreb index $M_1$ is constant for all trees in $\mathcal{T}(\mathcal{D})$, characterizing these extremal trees is tantamount to identifying those which minimize and maximize the second Zagreb index $M_2$ over the set $\mathcal{T}(\mathcal{D})$. Andriantiana et al. [1] established that the concept of $\text{Gut}_{\max}(T)$ over the class $\mathcal{T}(\mathcal{D})$ is attained by a tree constructed via a greedy method
termed the *Havel-Hakimi-type branching*. Specifically, this construction proceeds by iteratively connecting the vertex of the next highest degree to the current vertex possessing the highest remaining degree. Such a tree is frequently referred to as the *greedy tree* or the *maximum-degree-greedy tree* associated with the degree sequence $\mathcal{D}$. Consequently, the maximizing tree $T_{\max}(\mathcal{D})$ is characterized as *known and unique* up to graph isomorphism. The knowledge concerning the *minimum* is extremely limited in the general case. Only a small number of particular instances have been resolved:

* When the degree sequence $\mathcal{D}$ contains at most one vertex $v_\ell \in V(T)$ with degree $d_T(v_\ell) \ge 3$ (i.e., when $\mathcal{D}$ corresponds to a *spider* or a *double star* sequence), the unique tree associated with that sequence serves simultaneously as both the minimizer and maximizer.

* When all degrees are bounded by 3, and the sequence is *threshold* or exhibits other symmetries, partial results have been established.

* For all other cases, even the precise structure of $T_{\min}(\mathcal{D})$ remains conjectural.

**Problem 2.** Determine a closed-form formula for the difference

$$M_2(\mathbb{C}_{\max}(\mathcal{D})) - M_2(\mathbb{C}_{\min}(\mathcal{D}))$$

over caterpillar trees with degree sequence $\mathcal{D}$.

In contrast to caterpillars, which possess a linear spine imposing a total order on the placement of branches, general trees permit arbitrary branching and nested subtrees. The rearrangement of a pendent subtree can substantially reduce the number of high-degree adjacencies while preserving the degree sequence.

From a chemical standpoint, the tree $T_{\min}(\mathcal{D})$ corresponds to the alkane isomer characterized by a fixed branching pattern $\mathcal{D}$ that exhibits the *minimal* value of properties correlated with the Gutman and Zagreb indices, such as boiling point and enthalpy of vaporization. Identifying the structure of this tree would yield the absolute extremal molecule within each isomeric class.

Even establishing that $T_{\min}(\mathcal{D})$ is always realized by a *caterpillar* – that is, demonstrating that $\mathbb{C}_{\min}(\mathcal{D})$. coincides with the global minimum – would constitute a significant breakthrough. However, numerical evidence obtained from random degree sequences [13] of size $n \le 60$ indicates that non-caterpillar trees may achieve strictly smaller values by 1–5%.

Therefore, resolving Open Problems 1 and 2 regarding the minimum would bridge one of the most prominent gaps remaining in the study of degree-sequence-constrained extremal problems for Zagreb-type indices. Such a resolution would have immediate implications for applications in mathematical chemistry.

## 4. ON THE GUTMAN INDEX OF CATERPILLAR TREES

In this section, through Lemma 4.1, we exemplify the intimate relevance of Gut($G$) and $W(G)$ across caterpillar trees. This relevance reflects the significance of the interconnection of topological indices and the reflection in the chemical graph theory.

**Lemma 4.1.** Let $T_\ell(m_1, m_2, \dots, m_\ell)$ be a tree with a path containing $\ell$-th vertices where $n \equiv (\ell-2) (\mod (\ell-1))$. If Gutman index satisfy

$$\text{Gut}(G) = \frac{8(n-2)(n+1)}{3},$$

then

$$(8) \qquad \text{Gut}(G) = n^2 W_{n_i} + n W_{n_i n_j} + W_{n_j}.$$

*Proof.* Consider a tree $T$ in which every internal (non-leaf) vertex has degree exactly 4 and every leaf has degree 1. Such trees are known as $(1, i)$-trees (equivalently, trees with no vertices of degree
2, 3, ..., $i-1$). Let $n_i$ denote the number of internal vertices of degree $i$ and $n_j$ the number of leaves (degree-1 vertices). Then,

$$ (9) \qquad n_j = 2n_i + 2, \quad n = n_i + n_j = 3n_i + 2. $$

Thus, by using induction mathematics we noticed that:

Case 1: Given the degree sequence $d_G(u) = 4$ for all $u \in n_i$ and $d_G(v) = 1$ for all $v \in n_j$, according to (9) yielding

$$ (10) \qquad \text{Gut}(G) = 16 \sum_{\{u,v\} \subseteq n_i} \text{dist}_G(u, v) + 4 \sum_{u \in n_i, v \in n_j} \text{dist}_G(u, v) + \sum_{\{u,v\} \subseteq n_j} \text{dist}_G(u, v). $$

It follows immediately that $n \equiv 2 \pmod 3$ and $n_i = (n-2)/3$. It has been established in the chemical graph theory literature [15, 3, 2] that all (1, i)-trees on the same number of vertices $n$ possess identical Gutman indices, irrespective of their particular branching configuration. According to (10), the exact closed-form expression for the Gutman index of any such tree is

$$ (11) \qquad \text{Gut}(G) = \frac{8(n-2)(n+1)}{3}, $$

valid for every (1, 4)-tree $G$ with $n \ge 5$ and $n \equiv 2 \pmod 3$. Therefore, by introducing the auxiliary distance sums

$$ W_{n_i} = \sum_{\{u,v\} \subseteq n_i} \text{dist}_G(u, v), \quad W_{n_i n_j} = \sum_{u \in n_i, v \in n_j} \text{dist}_G(u, v), \quad \text{and} \quad W_{n_j} = \sum_{\{u,v\} \subseteq n_j} \text{dist}_G(u, v). $$

The Gutman index admits according to (1) the compact (10) form

$$ \text{Gut}(G) = 16 W_{n_i} + 4 W_{n_i n_j} + W_{n_j}. $$

Thus, for any tree satisfying the given degree conditions (internal vertices of degree exactly 4 and all remaining vertices pendent), the Gutman index is completely determined by the three weighted Wiener-type contributions $W_{n_i}$, $W_{n_i n_j}$, and $W_{n_j}$ defined above.

Case 2: Given the degree sequence $d_G(u) = 5$ for all $u \in n_i$ and $d_G(v) = 1$ for all $v \in n_j$, according to (9) yielding

$$ (12) \qquad \text{Gut}(G) = 25 \sum_{\{u,v\} \subseteq n_i} \text{dist}_G(u, v) + 5 \sum_{u \in n_i, v \in n_j} \text{dist}_G(u, v) + \sum_{\{u,v\} \subseteq n_j} \text{dist}_G(u, v). $$

Thus, according to (12) we find that

$$ \text{Gut}(G) = 25 W_{n_i} + 5 W_{n_i n_j} + W_{n_j}. $$

Note that, if $W_{n_i} = W_{n_j}$, this becomes $n^2 W_{n_i} + n W_{n_i n_j} + W_{n_j} = (n^2 + 1) W_{n_i} + n W_{n_i n_j}$. Thus, consider the identity:

$$ d_G(u) = \sum_{k=1}^{n} \eta_{ik} d_G(u) $$

Then,

$$ (13) \qquad \sum_{\{u,v\} \subseteq V(G)} d_G(u) d_G(v) \text{dist}(u, v) = \sum_{\{u,v\} \subseteq V(G)} \left( \sum_{k=1}^{n} \eta_{ik} \right) d_G(u) d_G(v) \text{dist}(u, v). $$

Thus, according to (13) the Gutman index satisfy

$$ (14) \qquad \text{Gut}(G) = \sum_{k=1}^{n} \sum_{\{u,v\} \subseteq V(G)} \eta_{ik} d_G(u) d_G(v) \text{dist}(u, v). $$
The relationship (14) holds $W_{n_i} = n W_{n_i n_j} + W_{n_i}$, when $i = k$. Finally, given the degree sequence $d_G(u) = n$ for all $u \in n_i$ and $d_G(v) = 1$ for all $v \in n_j$ for (5). Then

$$ \text{Gut}(G) = n^2 W_{n_i} + n W_{n_i n_j} + W_{n_j}. $$

As desire.

<figure><img src="image_4.png" /></figure>

The relationship of Gutman index and caterpillar tree had provided among Lemma 4.2.

**Lemma 4.2.** Let $T = \mathbb{C}(n, p)$ be a caterpillar tree with degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$. Then, the Gutman index is

$$ (15) \qquad \text{Gut}(\mathbb{C}(n, p)) = \sum_{i=1}^{n} pd_i + \sum_{i=1}^{n/2} d_{2i-1}d_{2i} + \sum_{i=2}^{n-1} d_i d_{i+1}. $$

*Proof.* Let $T = \mathbb{C}(n, p)$ be a caterpillar tree with degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_1 \le d_2 \le \dots \le d_{n-1} \le d_n$. by induction for $p = 3$ and $p = 4$ we find that among the following cases:

Case 1: Let $\mathbb{C}(n, 3)$ be a caterpillar tree illustrations by Figure 3. The degree of $v_1$ denote by $d_1$, the degree of $v_2$ denote by $d_2$, ... and the degree of $v_n$ denote by $d_n$.

<figure><img src="image_5.png" /><figcaption>FIGURE 3. Caterpillar tree $\mathbb{C}(n, 3)$.</figcaption></figure>

Thus, assume the degree sequence satisfy $3 \le d_1 \le d_2 \le \dots \le d_{n-1} \le d_n$. Then, we noticed that $d_1 + d_n \le \min\{\text{dist}(v_1, v_n)\}$ and $d_2 + d_{n-1} \le \min\{\text{dist}(v_2, v_{n-1})\}$. Thus,

$$ (16) \qquad \begin{cases} \sum_{k=1}^{n/2} (d_k + d_{n-k+1}) \le \min\{\text{dist}(v_k, v_{n-k+1})\} & \text{if } n \text{ even,} \\ \sum_{k=1}^{\lfloor n/2 \rfloor} (d_k + d_{n-k+1}) + d_{(n+1)/2} \le \min\{\frac{1}{2}\text{dist}(v_k, v_{n-k+1})\} & \text{if } n \text{ odd.} \end{cases} $$

Thus, from (16) we find that

$$ (17) \qquad \sum_{i=2}^{n-1} d_i d_{i+1} = \begin{cases} \sum_{k=1}^{n/2} (d_k + d_{n-k+1}) & \text{if } n \text{ even,} \\ \sum_{k=1}^{\lfloor n/2 \rfloor} (d_k + d_{n-k+1}) + d_{(n+1)/2} & \text{if } n \text{ odd.} \end{cases} $$

Therefore, according to (17) the Gutman index is

$$ (18) \qquad \text{Gut}(\mathbb{C}(n, 3)) = \sum_{i=1}^{n} 3d_i + \sum_{i=1}^{n/2} d_{2i-1}d_{2i} + \sum_{i=2}^{n-1} d_i d_{i+1}. $$

Case 2: Let $\mathbb{C}(n, 4)$ be a caterpillar tree. Then, clearly $4 \le d_1 \le d_2 \le \dots \le d_{n-1} \le d_n$. Then, we noticed that $d_1 + d_n \le \min\{\text{dist}(v_1, v_n)\}$ and $d_2 + d_{n-1} \le \min\{\text{dist}(v_2, v_{n-1})\}$. Thus,

$$ (19) \qquad \text{Gut}(\mathbb{C}(n, 4)) = \sum_{i=1}^{n} 4d_i + \sum_{i=1}^{n/2} d_{2i-1}d_{2i} + \sum_{i=2}^{n-1} d_i d_{i+1}. $$

Actually, from both cases, we noticed that according to (18) and (19) the first term change according to the pendent vertices. Thus, if $\mathbb{C}(n, p)$ be a caterpillar tree, then the relationship (15) holds.

<figure><img src="image_6.png" /></figure>
**Corollary 4.3.** Let $T = \mathbb{C}(n, p)$ be a caterpillar tree. Then

$$ 
\begin{aligned}
W(C(n, p)) &= n^3 + (p-1)n^2 - (p+1)n, \\
D'(C(n, p)) &= 2(p+6)n^3 - 6(p+4)n^2 + 2(p+2)n.
\end{aligned}
$$

For solve the problems such that we introduced in Section 3 we established Lemma 4.4 which it employees for Theorems 4.5 and 4.6. Thus, we consider $u$ and $v$ be vertices belonging to the spine, where $u$ lies closer to the center of the spine than does $v$. Unless the caterpillar tree is symmetric with respect to the vertex $u$, in which case equality may hold for certain positions symmetric to $v$. **Lemma 4.4.** Let $\mathbb{C}$ be caterpillar tree, the function $f_{\mathbb{C}}(\square)$ attains its minimum on the central portion of the spine and is strictly increasing as one moves away from this central portion toward either endpoint of the spine. Then $f_{\mathbb{C}}(u) < f_{\mathbb{C}}(v)$.

*Proof.* Let the spine be the path $P = (s_1, s_2, \dots, s_k)$. Moving a spine vertex $v = s_i$ one step toward the center of the path $P$ reduces the distance to every pendent leaf attached to spine vertices on the opposite side of $v$, whereas the distances to all remaining vertices either decrease or remain unchanged.

Consequently, the function $f_{\mathbb{C}}(\square)$ exhibits strict convex-like behavior along the spine: it attains its minimum near the center of the spine and increases monotonically toward both endpoints. $\square$

**Theorem 4.5.** Let $\mathcal{T}(\mathbb{C})$ be the class of trees over caterpillar tree with degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_1 \ge d_2 \ge \dots \ge d_n$. If $T_{\min}(\mathcal{D}) \in \mathcal{T}$. Then

$$ (20) \qquad \mathrm{Gut}(T_{\min}(\mathcal{D})) = \min_{T \in \mathcal{T}(\mathcal{D})} \mathrm{Gut}(T). $$

*Proof.* Assume $\mathcal{T}(\mathbb{C})$ be the class of trees over caterpillar tree with degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_1 \ge d_2 \ge \dots \ge d_n$. Recall Gutman index of a tree $T$ according to Lemma 4.4 as

$$ (21) \qquad \mathrm{Gut}(T) = \sum_{v \in V(T)} d_G(v) \cdot f_{\mathbb{C}}(v), \quad \text{where } f_{\mathbb{C}}(v) := \sum_{u \in V(T)} d_G(u) \cdot \mathrm{dist}_T(u, v). $$

Since the degree sequence $\mathcal{D}$ is fixed, the problem of minimising $\mathrm{Gut}(T)$ over the class of all caterpillars $T \in \mathcal{T}(\mathcal{D})$ is equivalent to minimising the weighted sum $\sum_v d_G(v) f_{\mathbb{C}}(v)$. This objective is achieved by placing vertices of higher degree at spine positions $v$ for which the value of $f_{\mathbb{C}}(v)$ is as small as possible.

Consider an arbitrary caterpillar $T \in \mathcal{T}(\mathcal{D})$ that is not isomorphic to $T_{\min}(\mathcal{D})$. By the defining construction of $T_{\min}(\mathcal{D})$, according to (21) there exist two vertices $u$ and $v$ on the spine of $T$ satisfying

$$ (22) \qquad d_G(u) > d_G(v) \quad \text{and} \quad f_{\mathbb{C}}(u) > f_{\mathbb{C}}(v). $$

Thus, the vertex of higher degree is positioned farther from the centre of the spine than the vertex of lower degree.

Construct a new caterpillar $\mathbb{C}'$ by interchanging the positions of $u$ and $v$ on the spine while retaining all pendent subtrees originally attached to each vertex. This operation preserves both the caterpillar structure and the degree sequence $\mathcal{D}$. The resulting change in the Gutman index is

$$ 
\begin{aligned}
\mathrm{Gut}(\mathbb{C}') - \mathrm{Gut}(\mathbb{C}) &= d_G(u)f_{\mathbb{C}'}(u) + d_G(v)f_{\mathbb{C}'}(v) - d_G(u)f_{\mathbb{C}}(u) - d_G(v)f_{\mathbb{C}}(v) \\
&= d_G(u)f_{\mathbb{C}}(v) + d_G(v)f_{\mathbb{C}}(u) - d_G(u)f_{\mathbb{C}}(u) - d_G(v)f_{\mathbb{C}}(v) \\
&= (d_G(u) - d_G(v))(f_{\mathbb{C}}(v) - f_{\mathbb{C}}(u)) \\
&< 0,
\end{aligned}
$$

since $d_G(u) - d_G(v) > 0$ and $f_{\mathbb{C}}(v) - f_{\mathbb{C}}(u) < 0$. Consequently, $\mathrm{Gut}(\mathbb{C}') < \mathrm{Gut}(\mathbb{C})$. Repeating this interchange procedure–analogous to the bubble-sort algorithm–progressively moves every vertex of high degree toward the centre of the spine and terminates precisely at the caterpillar $T_{\min}(\mathcal{D})$.
It follows that every caterpillar distinct from $T_{\min}(\mathcal{D})$ can be transformed, via a finite sequence of such interchanges, into a caterpillar possessing a strictly smaller Gutman index. Therefore,

$$ (23) \qquad \text{Gut}(T_{\min}(\mathcal{D})) \le \text{Gut}(T) \quad \text{for all } T \in \mathcal{T}(\mathcal{D}), $$

with equality if and only if $T$ is isomorphic to $T_{\min}(\mathcal{D})$ (up to reflection of the spine). Hence, from (21)–(23) we find that the relationship (20) holds. $\square$

**Theorem 4.6.** Let $\mathcal{T}(\mathbb{C})$ be the class of trees over caterpillar tree with degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_1 \ge d_2 \ge \dots \ge d_n$. If $T_{\max}(\mathcal{D}) \in \mathcal{T}$. Then

$$ (24) \qquad \text{Gut}(T_{\max}(\mathcal{D})) = \max_{T \in \mathcal{T}(\mathcal{D})} \text{Gut}(T). $$

*Proof.* For a fixed degree sequence $\mathcal{D}$, the problem of maximising the Gutman index $\text{Gut}_{\max}(T)$ over all caterpillars is equivalent to assigning vertices of large degree to spine positions where the function $f_{\mathbb{C}}(v)$ attains its largest possible values.

According to Theorem 4.5 and Lemma 4.4, the function $f_{\mathbb{C}}(v)$ is a convex quadratic function along the spine: it achieves its minimum at the centre of the spine and increases strictly towards the two endpoints. Consequently, the maximum values of $f_{\mathbb{C}}(v)$ are attained at the endpoints of the spine.

Let $\mathbb{C} \in \mathcal{T}(\mathcal{D})$ be a caterpillar that is not isomorphic to $\mathbb{C}_{\max}(\mathcal{D})$. By the construction of $\mathbb{C}_{\max}(\mathcal{D})$, there exist spine vertices $u$ and $v$ such that

$$ (25) \qquad d_G(u) > d_G(v) \quad \text{and} \quad f_{\mathbb{C}}(v) < f_{\mathbb{C}}(u) $$

(that is, the vertex of higher degree is positioned closer to the centre of the spine than the vertex of lower degree).

Consider the caterpillar $\mathbb{C}'$ obtained by interchanging the positions of $u$ and $v$ on the spine while keeping all pendent subtrees unchanged. The resulting change in the Gutman index is

$$ \begin{aligned} \text{Gut}(\mathbb{C}') - \text{Gut}(\mathbb{C}) &= d_G(u)f_{\mathbb{C}}(v) + d_G(v)f_{\mathbb{C}}(u) - d_G(u)f_{\mathbb{C}}(u) - d_G(v)f_{\mathbb{C}}(v) \\ &= (d_G(u) - d_G(v))(f_{\mathbb{C}}(v) - f_{\mathbb{C}}(u)) \\ &> 0, \end{aligned} $$

since $d_G(u) - d_G(v) > 0$ and $f_{\mathbb{C}}(v) - f_{\mathbb{C}}(u) > 0$. Thus, $\text{Gut}(\mathbb{C}') > \text{Gut}(T)$. Repeated application of this interchange operation, which systematically moves vertices of higher degree towards the endpoints of the spine, must terminate at the caterpillar $\mathbb{C}_{\max}(\mathcal{D})$. Therefore, every caterpillar distinct from $\mathbb{C}_{\max}(\mathcal{D})$ can be transformed into another caterpillar with a strictly larger Gutman index. It follows that from (25) the relationship (24) holds. $\square$

**Corollary 4.7.** For any degree sequence $\mathcal{D}$ realizable by a caterpillar tree $\mathbb{C}$,

$$ \text{Gut}(T_{\min}(\mathcal{D})) \le \text{Gut}(T) \le \text{Gut}(T_{\max}(\mathcal{D})) \quad \forall T \in \mathcal{T}(\mathcal{D}). $$

**Theorem 4.8.** For $\mathbb{C}$ a caterpillar tree, $\mathcal{D} = (d_1, \dots, d_n)$ be a degree sequence with $n \ge 3$, such that

$$ d_n > d_1 > d_{n-2} > \dots > d_3 > d_2 > d_{n-1}. $$

Then the caterpillar tree with this ordering attains the maximum value of Gut among all caterpillar trees whose path vertices have the degree sequence $\mathcal{D}$.

*Proof.* Assume $\mathbb{C}$ be a caterpillar tree with spine $P = (p_1, p_2, \dots, p_k)$, where $k \ge 3$, and let the degrees of the spine vertices $p_1, \dots, p_k$ be $d_1, d_2, \dots, d_k$ (in some order). It is well known that the Gutman index of a caterpillar satisfies

$$ (26) \qquad \text{Gut}(\mathbb{C}) = \sum_{i=1}^{k} d_{p_i} \cdot f_{\mathbb{C}}(p_i) + \eta, \quad \text{where} \quad f_{\mathbb{C}}(p_i) = \sum_{x \in V(\mathbb{C})} \text{dist}_{\mathbb{C}}(x, p_i). $$
Thus, the Wiener distance from all vertices to the spine vertex $p_i$, and $\eta \in \mathbb{Z}$ is a constant that depends solely on the number of pendent leaves attached to each spine vertex (and is independent of the ordering of the degrees along the spine).

Consequently, for a fixed spine length and fixed collection of pendent subtrees, maximizing Gut($\mathbb{C}$) is equivalent to maximizing the weighted sum ( according to Theorem 4.6)

$$ (27) \qquad S(\tilde{x}) := \sum_{i=1}^{k} d_{\tilde{x}(i)} f_{\mathbb{C}}(p_i) $$

over all permutations $\tilde{x}$ of the degree sequence $\mathcal{D}$. For fixed spine length $k$ and fixed pendent subtrees, the sequence $\mathcal{A}(f_{\mathbb{C}}) = (f_{\mathbb{C}}(p_1), f_{\mathbb{C}}(p_2), \dots, f_{\mathbb{C}}(p_k))$ satisfy $f_{\mathbb{C}}(p_i) = f_{\mathbb{C}}(p_{k+1-i})$ for all $i = 1, \dots, k$. Then

$$ (28) \qquad f_{\mathbb{C}}(p_{i-1}) - f_{\mathbb{C}}(p_i) < f_{\mathbb{C}}(p_i) - f_{\mathbb{C}}(p_{i+1}) $$

where $1 < i < k$. Thus, from (27) and (28) we obtained on

$$ f_{\mathbb{C}}(p_1) = f_{\mathbb{C}}(p_k) > f_{\mathbb{C}}(p_2) = f_{\mathbb{C}}(p_{k-1}) > \dots $$

Thus, the two largest values of $f_{\mathbb{C}}$ occur at the endpoints, the next two largest at positions 2 and $k-1$, and so forth, yielding a sequence that is strictly decreasing when read from either endpoint toward the centre. The optimal assignment of degrees to spine positions shown in Table 1 is therefore uniquely determined as follows:

<table><caption>TABLE 1. Optimal assignment of degrees to spine positions.</caption><thead><tr><th>Position <i>i</i></th><th>Assigned vertex</th><th>Degree (rank)</th></tr></thead><tbody><tr><td>1</td><td><i>v</i><sub>n</sub></td><td><i>d</i><sub>n</sub> (largest)</td></tr><tr><td>2</td><td><i>v</i><sub>1</sub></td><td><i>d</i><sub>1</sub> (2nd largest)</td></tr><tr><td>3</td><td><i>v</i><sub>n-2</sub></td><td><i>d</i><sub>n-2</sub> (3rd largest)</td></tr><tr><td>4</td><td><i>v</i><sub>3</sub></td><td><i>d</i><sub>3</sub> (4th largest)</td></tr><tr><td>...</td><td>...</td><td>...</td></tr><tr><td><i>k</i></td><td><i>v</i><sub>n-1</sub></td><td><i>d</i><sub>n-1</sub> (smallest)</td></tr></tbody></table>

Therefore, the vertices $v_1, \dots, v_n$ are labelled such that $d_1 \le d_2 \le \dots \le d_n$. Thus, the degree sequence is strictly decreasing when traversing the spine from either endpoint toward the centre.

Let $\mathcal{A}(f_{\mathbb{C}}) = (f_{\mathbb{C}}(p_1), f_{\mathbb{C}}(p_2), \dots, f_{\mathbb{C}}(p_k))$ and let $\mathcal{A}(f_{\mathbb{C}})^*$ denote the prescribed optimal degree sequence along the spine (as tabulated above). Both sequences are symmetric and strictly monotone decreasing from each endpoint inward. Thus, we noticed that $\mathcal{A}(f_{\mathbb{C}}) \neq \mathcal{A}(f_{\mathbb{C}})^*$. Then,

$$ (29) \qquad \sum_{i=1}^{k} f_{\mathbb{C}}(q_i) f_{\mathbb{C}}(p_i) < \sum_{i=1}^{k} f_{\mathbb{C}}(q_i)^* f_{\mathbb{C}}(p_i). $$

Hence, for any deviation from $\mathcal{A}(f_{\mathbb{C}})^*$ necessarily pairs some larger degree with a smaller $f_{\mathbb{C}}$-value and some smaller degree with a larger $f_{\mathbb{C}}$-value, while all inequalities among the degrees $d_j$ and among the successive differences of the $f_{\mathbb{C}}(p_i)$ are strict. Thus $S(\tilde{x})$ is uniquely maximized by the prescribed ordering $d_n > d_1 > d_{n-2} > \dots > d_3 > d_2 > d_{n-1}$, and hence Gut($\mathbb{C}$) is uniquely maximized by the corresponding caterpillar. $\square$

For the second problem 2, we presented Theorem 4.9 which it discussed a caterpillar obtained from $C(n, p)$ in Lemma 4.2.
**Theorem 4.9.** Let $\mathbb{C}(n, p, k, \ell_1, \dots, \ell_m)$ be the caterpillar obtained from $\mathbb{C}(n, p)$ by $m+1$ successive uniform pendant extensions with branching factors $k, \ell_1, \dots, \ell_m$, satisfying $p \le k \le \ell_1 \le \dots \le \ell_m$. Consider $\Lambda = k + \ell_1 + \ell_1\ell_2 + \dots + \ell_1\ell_1\dots\ell_m$. Then

$$M_1(\mathbb{C}(n, p, k, \ell_1, \dots, \ell_m)) = n(p + 2\Lambda)^2 + 4n + 2p,$$

$$M_2(\mathbb{C}(n, p, k, \ell_1, \dots, \ell_m)) = n(p + 2\Lambda)^2 + 3npk(p + 2\Lambda) + 4n + 2p.$$

*Proof.* By using induction mathematics, we discussed the following cases by recall Lemma 4.2 and Corollary 4.3.

**Case 1:** The vertex set of $C(n, p)$ is partitioned as follows: Two spine endpoints, each of degree $p+1$ (for $n \ge 2$; when $n=1$, there is only one spine vertex), $n-2$ internal spine vertices, each of degree $p+2$ (for $n \ge 3$; this term is zero otherwise), $np$ pendant leaves, each of degree 1. Thus,

$$M_1(\mathbb{C}(n, p)) = 2(p+1)^2 \mathbf{1}_{n \ge 2} + (n-2)(p+2)^2 \mathbf{1}_{n \ge 3} + \begin{cases} p^2 & \text{if } n=1 \\ 0 & \text{otherwise} \end{cases} + np \cdot 1^2.$$

For $n \ge 2$, expanding yields

$$\begin{aligned}
M_1(\mathbb{C}(n, p)) &= 2(p^2 + 2p + 1) + (n-2)(p^2 + 4p + 4) + np \\
&= 2p^2 + 4p + 2 + np^2 + 4np + 4n - 2p^2 - 8p - 8 + np \\
&= np^2 + 4np + 4n + 2p.
\end{aligned}$$

This holds for $n=1$ (where $\mathbb{C}(1, p)$ is the star $K_{1,p}$) and for $p=0$ (where $\mathbb{C}(n, 0) = P_n$). Therefore, the formula is valid for all $n \ge 1$, $p \ge 0$. Hence,

$$\begin{aligned}
M_2(\mathbb{C}(n, p)) &= 2(p+1)(p+2) + (n-3)(p+2)^2 + 2p(p+1) + (n-2)p(p+2) \\
&= (n-1)(p+2)^2 + 2p(p+1) + (n-2)p(p+2).
\end{aligned}$$

Therefore,

$$(n-1)(p+2)^2 = (n-1)(p^2 + 4p + 4) = np^2 + 4np + 4n - p^2 - 4p - 4,$$

$$2p(p+1) = 2p^2 + 2p,$$

$$(n-2)p(p+2) = np^2 + 2np - 2p^2 - 4p.$$

Then, we have

$$M_2(\mathbb{C}(n, p)) = np^2 + 4np + p^2 + 4n + 2p.$$

**Case 2:** The tree $\mathbb{C}(n, p, k)$ consists of four vertex types: Two spine endpoints (for $n \ge 2$), each with degree $p+1$, $n-2$ internal spine vertices (for $n \ge 3$), each with degree $p+2$, $np$ "first-level" leaves (original pendant vertices of $\mathbb{C}(n, p)$), each now of degree $k+1$ (connected to the spine and $k$ new leaves), and $npk$ "second-level" leaves (newest pendant vertices), each of degree 1. Thus,

$$\begin{aligned}
M_1(\mathbb{C}(n, p, k)) &= 2(p+1)^2 + (n-2)(p+2)^2 + np(k+1)^2 + npk \cdot 1^2 \\
&= 2(p^2 + 2p + 1) + (n-2)(p^2 + 4p + 4) + np(k^2 + 2k + 1) + npk \\
&= np^2 + 4npk^2 + 4np + 4npk + 4n + 2p \\
&= n(p + 2k)^2 + 4npk + 4n + 2p.
\end{aligned}$$

Then, by considering

(1) Spine edges ($n-1$ total):

(a) Two edges of type $(p+1)(p+2)$

(b) $n-3$ edges of type $(p+2)(p+2)$

(c) Contribution: $(n-1)(p+2)^2$.
(2) Edges from spine to first-level leaves ($np$ total):

(a) $2p$ edges of type $(p+1)(k+1)$

(b) $(n-2)p$ edges of type $(p+2)(k+1)$

(c) Contribution: $np(p+2)(k+1)$

(3) Edges from first-level to second-level leaves ($npk$ total): Each of type $(k+1) \cdot 1$ with contribution $npk(k+1)$

Thus,

$$ 
\begin{aligned}
M_2(\mathbb{C}(n, p, k)) &= (n-1)(p+2)^2 + np(p+2)(k+1) + npk(k+1) \\
&= (n-1)(p+2)^2 + np(k+1)(p+k+2).
\end{aligned}
$$

Then, we find that

$$ 
\begin{aligned}
(n-1)(p+2)^2 &= np^2 + 4np + 4n - p^2 - 4p - 4, \\
np(k+1)(p+k+2) &= np^2k + npk^2 + 3npk + np^2 + npk + 2np,
\end{aligned}
$$

Thus,

$$ M_2(\mathbb{C}(n, p, k)) = n(p+2k)^2 + npk(3p+4k) + 4n+2p. $$

These formulas also hold for boundary cases such as $n=1, p=0, k=0$ (where $\mathbb{C}(n, 0, 0) = P_n$ and $\mathbb{C}(n, p, 0) = \mathbb{C}(n, p)$), and $k=p$.

Case 3: For $\mathbb{C}(n, p, k, r)$ has four layers of vertices (with $n \ge 1, p \ge 0, 0 \le r \le k \le p$ integers). The first and second Zagreb indices are

$$ M_1(\mathbb{C}(n, p, k, r)) = n(p + 2k + 2kr)^2 + 4n(pk + pr + k^2r) + 4n + 2p $$

$$ M_2(\mathbb{C}(n, p, k, r)) = n(p + 2k + 2kr)^2 + npk(3p + 4k + 4kr) + npr(3p + 4kr) + 4n + 2p. $$

Every spine vertex has degree exactly $p+2\Lambda$, as each of the $np$ original leaves supports a subtree of $\Lambda$ new vertices, contributing $2\Lambda$ to the degree increase of its spine vertex (one from the original leaf and one from the subtree).

Consequently, the $n$ spine vertices contribute $n(p+2\Lambda)^2$ to both the $M_1$ index and the primary term of the $M_2$ index. All other vertices are either leaves (degree 1) or internal vertices of the pendant subtrees; their degree-squared sums cancel with the cross terms in the handshaking re-formulation of the Zagreb indices. The remaining contributions are: the original spine edges and endpoint adjustments amounting to $4n+2p$ in both indices, and the $np$ edges between the spine and first-level vertices, each contributing $(p+2\Lambda)(k+1)$, which simplifies to the additional term $3npk(p+2\Lambda)$ in $M_2$. $\square$

For the degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_T(v_i) = d_i$ for $i = 1, \dots, n$. Theorem 4.10 had established for $\mathcal{D}'(T)$ and $\text{Gut}(T)$ with constant term $\min\{\text{dist}(T)\{u, v\}\}$.

**Theorem 4.10.** Let $T = (V, E)$ be a tree with vertex set given as $V(T) = \{v_1, v_2, \dots, v_n\}$, $n \ge 2$ and degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_T(v_i) = d_i$ for $i = 1, \dots, n$. Then, for $uv \in E(T)$,

$$ 
\begin{aligned}
\mathcal{D}'(T) &= 2(n-1) \sum_{i=1}^{n} d_i(n-d_i) + \min\{\text{dist}(T)\{u,v\}\}, \\
(30) \qquad \text{Gut}(T) &= 2(n-1) \sum_{i=1}^{n} d_i(d_i-1) + \min\{\text{dist}(T)\{u,v\}\}.
\end{aligned}
$$

*Proof.* Assume the degree sequence $\mathcal{D} = (d_1, d_2, \dots, d_n)$ where $d_T(v_i) = d_i$ for $i = 1, \dots, n$. Consider $d_1 > d_2 > \dots > d_n$. Then, we need to prove the following claims:
Claim 1: For $uv \in E(T)$,

$$ (31) \qquad \sum_{\{u,v\} \subseteq V(T)} \mathrm{dist}(u, v) = n - 1. $$

Let $E(T) = \{e_1, e_2, \dots, e_m\}$. For $\ell \in E(T)$ there are $v_\ell(n - v_\ell)$ holds $\ell$ for the shortest paths $v_\ell(n - v_\ell)$, where $v_\ell$ is the number of vertices in one component of $T - \ell$. Thus, the relationship (31) holds.

Claim 2: For any function $f: V(T) \to \mathbb{R}$ satisfy

$$ (32) \qquad \sum_{\{u,v\} \subseteq V} f(u) \mathrm{dist}_T(u, v) = (n-1) \sum_{i=1}^{n} d_i f(v_i) - \sum_{i=1}^{n} f(v_i). $$

Actually, if $u \neq v$, then we find that

$$ (33) \qquad 2 \sum_{\{u,v\} \subseteq V} f(u) \mathrm{dist}_T(u, v) = \sum_{\{u,v\} \subseteq V, u \neq v} f(u) \mathrm{dist}_T(u, v). $$

Therefore, by considering $d_u = \mathrm{dist}_T(u, v)$ and $u \neq v$, by applying Claim 1 among (31) we noticed that

$$ (34) \qquad 2 \sum_{\{u,v\} \subseteq V} f(u) \mathrm{dist}_T(u, v) = (n-1)d_u - (n-1) + \min\{\mathrm{dist}(T)\{u,v\}\}. $$

Thus, from (33) and (34) the relationship (32) holds.

Now, by applying Claim 2 with $f(v) = d(v)$ and $u \neq v$, we noticed that

$$ \begin{aligned} \mathcal{D}'(T) &= \sum_{\{u,v\} \subseteq V} f(u) \mathrm{dist}_T(u, v) \\ &= (n-1) \sum_{i=1}^{n} d_i^2 - \sum_{i=1}^{n} d_i \\ &= 2(n-1) \sum_{i=1}^{n} d_i^2 - 2 \sum_{i=1}^{n} d_i \\ &= 2(n-1) \sum_{i=1}^{n} d_i^2 - 4(n-1) \\ &= 2(n-1) \left( \sum_{i=1}^{n} d_i^2 - 2 \right) \\ &= 2(n-1) \sum_{i=1}^{n} d_i(n - d_i) + \min\{\mathrm{dist}(T)\{u,v\}\}. \end{aligned} $$

For Gutman index, we know the Gutman index can be bounded as $\delta \mathcal{D}'(T) \le 2 \mathrm{Gut}(T) \le \Delta \mathcal{D}'(T)$ where $\delta$ is the minimum degree in $T$ and $\Delta$ is the maximum degree in $T$. Thus, it implies that
$d_T(u)d_T(v) \le \Delta(d_T(u) + d_T(v))$. Hence

$$
\begin{align*}
\text{Gut}(T) &= \sum_{\{u,v\} \subseteq V(T)} d_T(u)d_T(v) \operatorname{dist}_T(u, v) \\
&= (n-1) \sum_{i=1}^{n} d_i(d_i - 1) \\
&= 2(n-1) \sum_{i=1}^{n} d_i(d_i - 1) + \min\{\operatorname{dist}(T)\{u, v\}\}.
\end{align*}
$$

The completes the proof.

<figure><img src="image_7.png" /></figure>

The condition $d_1 > d_2 > \cdots > d_n$ (strictly decreasing with all distinct degrees) stated in the original question is unnecessary: the relationship (30) remain exact and represent unique closed-form expressions that depend solely on the degrees, irrespective of whether the degrees are distinct or strictly ordered.

Example 1: The path graph $P_n$ has a degree sequence consisting of two vertices of degree 1 and $n-2$ vertices of degree 2. Thus,

$$
\sum_{i=1}^{n} d_i(nd_i) = 2(n-1) + 2(n-2)^2, \quad \sum_{i=1}^{n} d_i(d_i - 1) = 2(n-2).
$$

Therefore, we obtained that $\mathcal{D}'(P_n) = 4(n-1)(n^2 - 3n + 3)$ and $\text{Gut}(P_n) = 4(n-1)(n-2)$.

Example 2: Let $n \ge 3$, for the star tree $S_n$, we noticed that it has one vertex of degree $n-1$ and $n-1$ leaves of degree 1. Thus

$$
\sum_{i=1}^{n} d_i(nd_i) = n(n-1), \quad \sum_{i=1}^{n} d_i(d_i - 1) = (n-1)(n-2).
$$

Therefore, we obtained that $\mathcal{D}'(S_n) = 2n(n-1)^2$ and $\text{Gut}(S_n) = 2(n-1)^2(n-2)$.

**Theorem 4.11.** Let $T = (V, E)$ be a binary tree of height $h \ge 1$ and root at level 0 with $n = 2^{h+1} - 1$ where $2^h$ leaves of degree 1, $2^h - 1$ internal vertices of degree 3.

$$
\begin{equation} \tag{35}
\begin{aligned}
\mathcal{D}'(T) &= 8(2^h - 1)(2^h - 2)(2^{h+1} - 1) + \min\{\operatorname{dist}(T)\{u, v\}\}, \\
\operatorname{Gut}(T) &= 12(2^{h+1} - 2)(2^h - 1) + \min\{\operatorname{dist}(T)\{u, v\}\}.
\end{aligned}
\end{equation}
$$

*Proof.* According to Theorem 4.10, by applying the relationship (30) we find that

$$
\begin{align*}
\sum_{i=1}^{n} d_i(n - d_i) &= 2^h \cdot 1 \cdot (n - 1) + (2^h - 1) \cdot 3 \cdot (n - 3) \\
&= 2^h (n - 1) + 3(2^h - 1)(2^{h+1} - 4) \\
&= (2^h - 1) [2^{h+1} \cdot 2^h + 3(2^{h+1} - 4)] \\
&= (2^h - 1) \cdot 4 \cdot (2^h - 2) \cdot (2^{h+1} - 1) \\
&= 4(2^h - 1)(2^h - 2)(2^{h+1} - 1) \\
&= 6(2^h - 1).
\end{align*}
$$
Thus, according to (30), we noticed that

$$
\begin{align*}
\mathcal{D}'(T) &= 2(n-1) \cdot 4 (2^h - 1)(2^h - 2)(2^{h+1} - 1) \\
&= 8(2^h - 1)(2^h - 2)(2^{h+1} - 1) \\
&= 8(2^h - 1)(2^h - 2)(2^{h+1} - 1) + \min\{\mathrm{dist}(T)\{u, v\}\}.
\end{align*}
$$

Similarly, for Gutman index the relationship (35) holds.

Example 3: Let $T = (V, E)$ be a binary tree of height $h \ge 1$ and root at level 0 with $n = 2^{h+1} - 1$. Then, among Table 2 we observe Theorem 4.11 for small value of $h$.

<table><caption>TABLE 2. Numerical verification for small $h$.</caption>
  <thead>
    <tr>
      <th>Height <i>h</i></th>
      <th><i>n</i></th>
      <th><i>D</i>'(<i>T</i>)</th>
      <th>Gut(<i>T</i>)</th>
      <th>Height <i>h</i></th>
      <th><i>n</i></th>
      <th><i>D</i>'(<i>T</i>)</th>
      <th>Gut(<i>T</i>)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>3</td>
      <td>24</td>
      <td>24</td>
      <td>2</td>
      <td>7</td>
      <td>480</td>
      <td>240</td>
    </tr>
    <tr>
      <td>3</td>
      <td>15</td>
      <td>5 888</td>
      <td>2 184</td>
      <td>4</td>
      <td>31</td>
      <td>57 600</td>
      <td>17 280</td>
    </tr>
    <tr>
      <td>5</td>
      <td>63</td>
      <td>516 096</td>
      <td>131 064</td>
      <td>6</td>
      <td>127</td>
      <td>4 456 960</td>
      <td>1 048 576</td>
    </tr>
  </tbody>
</table>

5. CONCLUSION

This study clarifies the interplay between vertex degrees and distances in determining the Gut-
man index of trees, focusing on caterpillars. It proves that the index is minimized when high-degree
vertices occupy central spine positions and maximized at spine endpoints. Closed-form expressions
for the Gutman and Zagreb indices of hierarchically pendant-extended caterpillars extend these
invariants to broader tree classes. These results and formulas support efficient computation and
deeper analysis of distance-degree invariants, enabling future studies on optimal degree arrange-
ments in general graphs.

ACKNOWLEDGEMENTS

The authors would like to express their sincere gratitude to the anonymous reviewers for their
insightful comments and constructive suggestions, which have substantially enhanced the clarity
and quality of this manuscript.

DECLARATIONS

* **Funding:** The authors received no external funding for this research.

* **Conflict of interest / Competing interests:** The authors declare that they have no conflicts of interest or competing interests related to this study.

* **Ethics approval and consent to participate:** Not applicable.

* **Data availability statement:** All data is included within the manuscript.

REFERENCES

[1] E. O. D. Andriantiana, S. Wagner, H. Wang, Spectral moments of trees with given degree sequence, *Linear Algebra Appl.* **439** (2013) 3980–4002.

[2] N. Bašić, M. Knor, R. Škrekovski, On regular graphs with Šoltes vertices, *Ars Math. Contemp.* **25**(2) (2025), #P2.01.

[3] S. Cambie, J. Haslegrave, On the relationship between variable Wiener index and variable Szeged index, *Appl. Math. Comput.* **431** (2022) #127320.

[4] G. Durand, N. Belacel, F. LaPlante, Graph theory based model for learning path recommendation, *Inf. Sci.* **251** (2013) 10–21.

[5] A. Dobrynin, A. Kochetova, Degree distance of a graph: a degree analogue of the wiener index, *J. Chem. Inf. Comput. Sci.* **34** (1994) 1082–1086.
[6] S. El Basil, Caterpillar (Gutman) trees in chemical graph theory, Topics Curr. Chem. 153 (1990), 273-292.

[7] I. Gutman, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci. 34 (1994) 1087-1089.

[8] I. Gutman, Gutman index – A critical personal account, Bull. Acad. Serbe Sci. Arts. (Cl. Sci. Math. Natur.) 46 (2021) 183-193.

[9] I. Gutman, B. Furtula, K. C. Das, On some degree-and-distance-based graph invariants of trees, Appl. Math. Comput. 289 (2016) 1-6.

[10] I. Gutman, S. Klavžar, Bounds for the Schultz molecular topological index of benzenoid systems in terms of the Wiener index, J. Chem. Inf. Comput. Sci. 37 (1997) 741-744.

[11] I. Gutman, B. Ruščić, N. Trinajstić, C. F. Wilcox, Graph theory and molecular orbitals. XII. Acyclic polyenes, Journal of Chemical Physics 62 (1975) 3399-3405.

[12] I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535-538.

[13] J. Hamoud, D. Abdullah, Behavior of the extremal bounds on the σ-irregularity, arXiv preprint. (2025) arXiv:2510.06845.

[14] H. Hosoya, K. Kawasaki, K. Mizutani, Topological index and thermodynamic properties. I. Empirical rules on the boiling point of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 45 (1972) 3415-3421.

[15] R. Kazemi, L. Meimondari, Degree distance and Gutman index of increasing trees, Trans. Comb. 5(2) (2016) 23-31.

[16] M. Knor, P. Potočnik, R. Škrekovski, Relationship between the edge-Wiener index and the Gutman index of a graph, Discr. Appl. Math. 167 (2014) 197-201.

[17] M. Knor, R. Škrekovski, A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Contemp. 11 (2016) 327-352.

[18] Y. Mao, K. C. Das, Steiner gutman index, MATCH Commun. Math. Comput. Chem, 79(3) (2018) 779-794.

[19] N. S. Schmuck, S. G. Wagner, H. Wang, Greedy trees, caterpillars, and Wiener-type graph invariants, MATCH Commun. Math. Comput. Chem. 68 (2012) 273-292.

[20] H. P. Schultz, Topological organic chemistry. 1. Graph theory and topological indices of alkanes, J. Chem. Inf. Comput. Sci. 29 (1989) 227-228.

[21] S. Shetty, B. R. Rakshith, N. S. Udupa, Extremal graphs and bounds for general Gutman index, AIMS Math. 9 (2024) 30454-30471.

[22] R. Todeschini, V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, 2010.

[23] S. Wagner, H. Wang, Introduction to Chemical Graph Theory, CRC Press, Boca Raton, 2018.

[24] H. Wang, K. Xu, The minimum Wiener index of Halin graphs with characteristic trees of diameter 4, El. J. Math. 9 (2025) 11-22.

[25] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17-20.

**JASEM HAMOUD:** PHYSICS AND TECHNOLOGY SCHOOL OF APPLIED MATHEMATICS AND INFORMATICS, MOSCOW INSTITUTE OF PHYSICS AND TECHNOLOGY.

Email address: jasem1994hamoud@gmail.com