# Degree Sequence of Albertson and $\sigma$-Indices on Trees of Order $n > 3$

Jasem Hamoud, Artem Kornosov

► To cite this version:

Jasem Hamoud, Artem Kornosov. Degree Sequence of Albertson and $\sigma$-Indices on Trees of Order $n > 3$. 67th All-Russian Scientific Conference of the Moscow Institute of Physics and Technology, Moscow Institute of Physics and Technology, Mar 2025, Moscow, Russia. hal-05104299

HAL Id: hal-05104299

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

Submitted on 9 Jun 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
Degree Sequence of Albertson and $\sigma$-Indices
on Trees of Order $n \ge 3$

Jasem Hamoud¹,*, Artem Kornosov¹,

¹ Discrete Mathematics

Moscow Institute of Physics and Technology (National Research University)

* Corresponding author. Email: khamud@phystech.edu

**Abstract.** In this paper, we presented a study of topological indices on trees, where we show a relationship with irregularity of Albertson index and minimum, maximum degrees $\delta, \Delta$ of graph $G$, where contribute vital roles in determining connection, shading, component incorporation, and realisability where well-known Albertson index as: $\text{irr}(G) = \sum_{uv \in E(G)} |d_u(G) - d_v(G)|$. The $\sigma$ index on trees that we introduced as $\sigma(T) = (d_1 - 1)^3 + \sum_{i=1}^3 (d_i - 1)(d_i - 2) + (d_3 - 1)^3$.

**Keywords:** Degree, Trees, Topological, Index.

**JEL Classification:** C6

**MSC Classification 2010:** Primary: 05C05, 90C35, Secondary: 68R10

# 1 Introduction

Throughout this paper*, let $G(E, V)$ be a simple, connected graph, denote by $uv$ an edge connecting vertices $u$ and $v$. Further, let $\text{deg} i = \text{deg}(i)$ the degree of a vertex $i$. In 1969, Harary, F. in [3] mention to a diverge at a vertex $u$ in a tree $T$ is its largest subtree which includes $u$ as a termination. Therefore, the amount of diverge at $u$ equals $\text{deg} u$, which for any tree has a center chord of a maximum of one or two points. In 1971, let be refer to the maximal number of edges by $\mathcal{E}$, Wai-Kai Chen in [4] refer to the graph $G$ has $n$ nodes and $c$ components, then $\mathcal{E} = \frac{1}{2}(n-c)(n-c+1)$, we can make it as a general case if $G_i, i = 1, 2, \dots, c$, is the components of $G$, each having $n_i$ nodes, then $\mathcal{E} = \frac{1}{2}n_i(n_i-1)$. Further, in 2009, Voloshin, V. I, in [7] consider a graph $G = (X, E)$, determine number known well as Szekeres-Wilf number:

$$M(G) = \max_{X' \subseteq X} \min_{x \in G'} d(x).$$

In 1997, M. O. Albertson in [2] mention to the imbalance of an edge $uv$ by $imb(uv) = |d_u - d_v|$, Considered graph $G$ regular if all of its vertices have the

<footnote>*This paper had discussed in Conference 67th All-Russian Scientific Conference of the Moscow Institute of Physics and Technology. (30 March – 5 April 2025)</footnote>
exact same degree, then irregularity measure define in [2, 8, 9] as:

$$ \mathrm{irr}(G) = \sum_{uv \in E(G)} |d_u(G) - d_v(G)|. $$

Dorjsembe, S et al. In [6] given a relationship with irregularity of Albertson index and minimum, maximum degrees $\delta$, $\Delta$ of graph $G$, where contribute vital roles in determining connection, shading, component incorporation, and realizability. Among this degrees, which reflect the maximum and minimum number of edges incident to every vertex in the graph, are important elements of a graph's sophistication and performance. It is given by: $\mathrm{irr}(G) > \frac{\delta(\Delta-\delta)^2 \cdot |V|}{\Delta+1}$, the degree sum formula (or handshaking lemma) is known well as doubles of edges as $2|E|$, the first and the second Zagreb index, $M_1(G)$ and $M_2(G)$ are defined in [2, 10, 12] as:

$$ M_1(G) = \sum_{i=1}^{n} d_i^2, \quad \text{and} \quad M_2(G) = \sum_{uv \in E(G)} d_u(G)d_v(G). $$

In [9, 11] define total irregularity as $\mathrm{irr}_T(G) = \sum_{\{u,v\} \subseteq V(G)} |d_u(G) - d_v(G)|$. When $G$ is a tree, Ghalavand, A. et al. In [16] proved $\mathrm{irr}_T(G) \le \frac{n^2}{4} \mathrm{irr}(G)$, in this case, they show $\mathrm{irr}_T(G) \le (n-2) \mathrm{irr}(G)$. The recently introduced $\sigma(G)$ irregularity index is a simple diversification of the previously established Albertson irregularity index, in [14, 15] defined as:

$$ \sigma(G) = \sum_{uv \in E(G)} (d_u(G) - d_v(G))^2. $$

This paper is organized as follows. In Section 2, we observe the important concepts to our work including literature view of most related papers, in Section 3 we computing the main result of this paper including Albertson and Sigma indices on caterpillar tree,

## 2 Preliminaries

In this section, we show in Lemma 1 the Albertson index with maximum and minimum degree $\Delta$, $\delta$, also we explain the relationship between Albertson index and Sigma index on star graph $S_n$ as we show in Lemma 2, 3. In Proposition 1, Collatz and Bell in [1, 19] show the maximum of Albertson index on the set of all $n$ vertex graph.
**Lemma 1.** [15, 20] Let $G(V, E)$ a graph (simple and connected), then:

$$ \mathrm{irr}(G) \leq \frac{(\Delta - \delta)}{\sqrt{\Delta \delta}} \sqrt{|E| \sum_{uv \in E(G)} d_G(u)d_G(v)}. $$

The sigma index, a graph-theoretic estimation of irregularity, is now recognised as an important tool for investigating architectural variance in networks. This index, estimated as the sum of squared degree differences between adjacent vertices.

**Theorem 1.** [21] Let be a complete bipartite graph is $K_{m,n}$, then sigma index of graph is $\sigma(K_{m,n}) = (mn)(n-m)^2$.

**Theorem 2.** [14] For any double star graph $S_{r,k}$, the degrees of two adjacent central vertices $u, v$ defined as $d_u = k \ge 3, d_v = r \ge 1$. Then the sigma index of $S_{r,k}$ is given by

$$ \sigma(S_{r,k}) = (k-1)^3 + k^2 + (r-1)^3 + r^2 - 2kr. $$

**Proposition 1.** Let be $\mathcal{G}(n)$ is the set of all $n$ vertex on graph $G$, $\lambda(G)$ the index of the largest eigenvalue in graph, and let be $\bar{\mathcal{d}}(G)$ the mean of the vertex degrees, then

$$ \mathrm{irr}(G) = \lambda(G) - \bar{\mathcal{d}}(G). $$

Then, we have:

$$ \max\{\mathrm{irr}(G) : G \in \mathcal{G}(n)\} = \begin{cases} \frac{1}{4}n - \frac{1}{2} & (n \text{ even }) \\ \frac{1}{4}n - \frac{1}{2} + \frac{1}{4n} & (n \text{ odd }) \end{cases}. $$

This result implies in [1, 2, 8, 19]. This relationship can be demonstrated for the indices in both Lemma 2, 3, which depict the star graph.

**Lemma 2.** [5] The star $S_n$ is the only tree of order $n$ that has a great deal of irregularity, satisfying:

$$ \mathrm{irr}(S_n) = (n - 2)(n - 1). $$

**Lemma 3.** Let be $\mathcal{T}$ a classes of trees, then $\sigma_{\max}, \sigma_{\min}$ in trees with $n$ vertices by:

$$ \sigma(\mathcal{T}) = \begin{cases} \sigma_{\max}(\mathcal{T}) = (n-1)(n-2); n \ge 3 \\ \sigma_{\min}(\mathcal{T}) = 0; n = 2. \end{cases} $$
According to a tree with $n$ vertices has $n-1$ edges, then we have $\sigma_{\max}(T) = n - 2$. Thus, the modified total Sigma as $\sigma_t(T) = \frac{1}{2} \sum_{(u,v) \subseteq V(T)} (d_u - d_v)^2$, show that in [17,18] and in Theorem 3, so that $\sigma_{t,\max} = (n-1)(n-2)^2$.

**Theorem 3.** [17] Let $G$ is a connected graph of order $n$ which $n \in \mathbb{N}$, $n \ge 3$ vertices it holds

$$ \sigma_t(G) \le \begin{cases} \lfloor \frac{n}{4} \rfloor \cdot \lfloor \frac{3n}{4} \rfloor (n - 1 - \lfloor \frac{n}{4} \rfloor)^2, & \text{if } n \equiv 0 \text{ mod } 4 \text{ or } n \equiv 3 \text{ mod } 4; \\ \lfloor \frac{n}{4} \rfloor \cdot \lfloor \frac{3n}{4} \rfloor (n - 1 - \lfloor \frac{n}{4} \rfloor)^2, & \text{if } n \equiv 1 \text{ mod } 4 \text{ or } n \equiv 2 \text{ mod } 4. \end{cases} $$

## 3 Main Result

We mention by $C(n, m)$ caterpillar tree with $(n, m)$ vertices, and refer to $n$ main vertices in figure 1 as we show.

<figure><img src="image_2.png" /><figcaption>**Figure 1.** Example of Caterpillars in graph theory.</figcaption></figure>

We have $X = (x_1, x_2, \dots, x_n)$ where $n = |X|$, and refer to $m$ a set of leaves adjacent to main vertices. Zhang, P., Wang, X in [13] show “Caterpillar trees” are employed in chemical graph theory for describing molecular structures, and several topological indices, which include the Albertson index, have been used to study the characteristics of molecules.

In Figure 2 we show some caterpillars trees $C(n, 3)$ for $n = 3, 4, 5, 6$:

<figure><img src="image_3.png" /><figcaption>**Figure 2.** Caterpillars tree with $(n, 3)$ vertices</figcaption></figure>

**Proposition 2.** *Albertson index of Caterpillar trees given by:*

$$ \mathrm{irr}(C(n, m)) = \begin{cases} m(m+1)n - 2m + 2, & \text{if } n \ge 3, \\ m(m+1)n - 2m, & \text{if } n \in \{1, 2\}. \end{cases} $$
*Proof.* We know $S_m$ is the graph star of order $m$, then Albertson index of star every edge combines the central vertex (degree $m$) with a pendant vertex (degree 1) given by $\text{irr} = m(m-1) = m(m+1)n - 2m$ for $n = 1$.

For greater $n$ let sequence $x_1, x_2, \dots, x_n$ be a central path of caterpillar and $y_{i,1}, \dots, y_{i,m}$ pendant vertices adjacent to $x_i$ (see figure 3). Then $\text{deg} x_1 = \text{deg} x_n = m+1$ and $\text{deg} x_i = m+2$ for $2 \le i \le n-1$.

<figure><img src="image_4.png" /><figcaption>Figure 3. General case of Caterpillar tree</figcaption></figure>

Firstly, for $n = 2$, we have depend main definition of Albertson index as:

$$ \text{irr}(G) = \sum_{j=1}^{m} |\text{deg } x_1 - \text{deg } y_{1,j}| + \sum_{j=1}^{m} |\text{deg } x_2 - \text{deg } y_{2,j}| = 2m(m+1-1) = 2m^2. $$

Then we have $m(m+1)n - 2m$ correct for $n = 2$.

Now let $n \ge 3$. So we can calculate $\text{irr}$ as we have $\sum_{j=1}^{m} |\text{deg } x_i - \text{deg } y_{i,j}|$, then we have:

$$ \sum_{j=1}^{m} |\text{deg } x_i - \text{deg } y_{i,j}| = \begin{cases} m^2, & \text{if } i = 1, i = n, \\ m(m+1), & \text{if } 2 \le i \le n-1. \end{cases} $$

Therefore, as we have $|\text{deg } x_1 - \text{deg } x_2| + \dots + |\text{deg } x_n - \text{deg } x_{n-1}| = 2$, the Albertson index is

$$ \text{irr}(C(n, m)) = 2m^2 + (m+1)m(n-2) + 2, $$

as desire.

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

**Proposition 3.** Let be $\text{irr}(C(n, 3))$ Albertson index of caterpillar tree of order $(n, 3)$ vertices, then we have:

$$ \text{irr}_{\max}(C(n, m)) = \text{irr}_{\min}(C(n, m)) = \text{irr}(C(n, m)). $$

This implies that we cannot specify $\text{irr}_{\max}$, $\text{irr}_{\min}$ in caterpillar tree $C(n, 3)$, or in other terms, there are no such values but only the general value of the Albertson index $\text{irr}$.
**Proposition 4.** *Sigma index for caterpillar tree of order (n, m) given by:*

$$ \sigma(C(n,m)) = \begin{cases} 2m^3, & \text{if } n = 2 \\ 2m^3 + m - 2, & \text{if } n \ge 2. \end{cases} $$

*Proof.* Assume the sequence $x_1, x_2, \dots, x_n$ and $y_{1,1}, \dots, y_{i,j}$ pendant vertices adjacent to $x_i$. Then $\deg x_1 = \deg x_n = m + 1$ and $\deg x_i = m + 2$ for $2 \le i \le n - 1$. from Figure 2 we have in fact, for $n = 2$, then Sigma index of caterpillar tree given as: $\sigma = 2m^3$, for $n = 3$, then we have: $\sigma = 2m^3 + m - 2$, therefore, we can express from Figure 3 that as:

$$ \sigma(C(n,m)) = \begin{cases} 2m^3, & \text{if } n = 2 \\ 2m^3 + m - 2, & \text{if } n \ge 2. \end{cases} $$

Then we have $(\deg x_1 - \deg x_2)^2 + \dots + (\deg x_{n+1} - \deg x_n)^2$ that is hold to:

$$ \sigma = \left( \sum_{j=1}^{n} \deg x_i - \deg y_{i,j} \right)^2 \quad \forall i \in \mathbb{N}. $$

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

**Proposition 5.** *For Caterpillar tree with path vertices with degrees $d_1, d_2, \dots, d_n$, we have:*

$$ \mathrm{irr}(G) = (d_n - 1)^2 + (d_1 - 1)^2 + \sum_{i=2}^{n-1} (d_i - 1)(d_i - 2) + \sum_{i=1}^{n-1} |d_i - d_{i+1}|. $$

**Hypothesize 1.** Let be a sequences with $n \ge 3$ and let be order as: $d_n > d_1 > \dots > d_2 > d_{n-1}$, the Caterpillar tree with such order has the maximum value of $\mathrm{irr}$ among all Caterpillar trees with such degrees sequence of path vertices.

*Proof.* By using Proposition 5 we have for $n = 3$, $d_1 \ge d_2 \ge d_3$, the maximum case is when $d_3$ is the degree of the central vertex of tree and from proposition 5, We can therefore generalise for example for $n = 3$, this to any sequence of degree $n$ is correct given by $d_n > d_1 > \dots > d_2 > d_{n-1}$. Such that:

$$ \mathrm{irr}(G) = (d_n - 1)^2 + (d_1 - 1)^2 + \sum_{i=2}^{n-2} (d_i - 1)(d_i - 2) + \sum_{i=1}^{n-1} |d_i - d_{i+1}|. $$

Now we need to prove that for $n + 1$ with the sequence is $d_{n+1} \ge d_1 \ge \dots \ge d_2 \ge d_n$, since $d_1 \ge d_n$, then we can simplify model the association as
$(d_n - 1)^2 = (d_n - 1)(d_n - 2) + (d_n - 1)$, further we have $d_1 = d_n + r \mid r \ge 0, r \in \mathbb{N}$, so that we have $(d_n - 1)^2 + (d_1 - 1) = (d_n)^2 - d_n + r$ and also for $\sum_{i=2}^{n-2} (d_i - 1)(d_i - 2)$ we have $\sum_{i=2}^{n-2} ((d_i)^2 - 3d_i + 2)$, then we have:

$$ (d_i - 1)(d_i - 2) = (d_i - 1)^2 + (d_i - 1) = (d_i)^2 - 3d_i + 2(n - 3). $$

where we consider $\sum_{i=2}^{n-2} 2 = 2(n - 3)$. Thus we can write it as:

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

Then we have:

$$ \mathrm{irr}(G) = (d_n - 1)(d_n - 2) + (d_n - 1) + \sum_{i=2}^{n-2} (d_i)^2 - 3 \sum_{i=2}^{n-2} d_i + 2(n - 3) + \sum_{i=1}^{n-1} |d_i - d_{i+1}|. $$

Therefore, we suppose $\sum_{i=1}^{n-1} |d_i - d_{i+1}| - \sum_{i=2}^{n-1} d_i$ is max for $n$ when $d_n > d_1 > \dots > d_2 > d_{n-1}$, then the question is why we consider:

$$ \sum_{i=1}^{n-1} |d_i - d_{i+1}| - \sum_{i=2}^{n-1} d_i $$

is max when $d_n > d_1 > \dots > d_2 > d_{n-1}$, so that, we need to prove the relationship is max for $n + 1$. In this case we have:

$$ \mathrm{irr}(G) = \sum_{i=1}^{n-1} |d_i - d_{i+1}| + (d_1 + d_n) $$

Assume $\sum_{i=1}^{n-1} |d_i - d_{i+1}| + d_1 + d_n$ is max when $d_n > d_1 > \dots > d_2 > d_{n-1}$, Therefore $\sum_{i=1}^{n-1} |d_i - d_{i+1}| + d_1 + d_{n+1}$ is max when $d_n > d_1 > \dots > d_2 > d_{n-1}$, we noticed that $d_1 + d_{n+1}$ is maximum value when $d_{n+1} \ge d_1 \ge \dots \ge d_2 \ge d_n$, then we need to prove $\sum_{i=1}^{n-1} |d_i - d_{i+1}|$ is maximum value when $d_{n+1} \ge d_1 \ge \dots \ge d_2 \ge d_n$, therefore, we have

$$ \mathrm{irr}(G) = \sum_{i=1}^{n-1} |d_i - d_{i+1}| + d_1 + d_{n+1} \\ = |d_1 - d_2| + |d_2 - d_3| + \dots + |d_{n-1} - d_n| + d_1 + d_{n+1} $$

Now, we have two cases that we can discuss as follows, In order to compare both $d_i$ and $d_{i+1}$ and to determine the maximised value of the term $\sum_{i=1}^{n-1} |d_i - d_{i+1}|$ according to $\mathrm{irr}(G)$ as:
**Case 1:** If $d_i \ge d_{i+1}$, then we have $\text{irr}(G) = 2d_1 - d_n + d_{n+1}$ is maximum, notice $2d_1$ comes from combining the two $d_1$ terms where $d_n+d_{n+1}$ is maximum when $d_{n+1} \ge d_1 \ge \dots \ge d_2 \ge d_n$.

**Case 2:** If $d_i \le d_{i+1}$, then we have $\text{irr}(G) = d_n + d_{n+1}$ is the maximum, so that in this case the term $\sum_{i=1}^{n-1} |d_i - d_{i+1}|$ is combined with the maximum value $d_1 + d_{n+1}$.

Thus, we have

$$ \text{irr}(G) = \begin{cases} 2d_1 - d_n + d_{n+1} & \text{if } d_i \ge d_{i+1}, \\ d_n + d_{n+1} & \text{if } d_i \le d_{i+1}. \end{cases} $$

is the maximum when $d_{n+1} \ge d_1 \ge \dots \ge d_2 \ge d_n$ and $d_1 + d_{n+1}$ is maximum. As desire. ■

## 3.1 Sigma Index and Albertson Index Among Trees

**Hypothesize 2.** Let $T$ be a tree of order $n \ge 2$, a degree sequence $d = (d_1, d_2, d_3)$ where $d_3 \ge d_2 \ge d_1$, then Sigma index given by:

$$ \sigma(T) = (d_1 - 1)^3 + \sum_{i=1}^{3} (d_i - 1)(d_i - 2) + (d_3 - 1)^3. $$

*Proof.* For the sequence $d(d_1, d_2, d_3)$, we will investigate all potential instances of this sequence that describe the positioning of each of these vertices as shown in Figure 4, which depicts the three principal cases we are considering as:

<figure><img src="image_7.png" /><figcaption>**Figure 4.** describe sequence $d(d_1, d_2, d_3)$.</figcaption></figure>

**Case 1:** in this case we have first recognize as $d(d_1, d_2, d_3)$, then we have:

$$ \begin{aligned} \sigma(T) &= d_1(d_1 - 1)^2 + d_2(d_2 - d_3)^2 + d_3(d_3 - d_2)^2 + 2 \\ &= d_1^3 - 2d_1^2 + d_1 + d_2^3 + d_3^3 - 4d_2d_3^2 + 2. \end{aligned} $$
**Case 2:** in this case we have the sequence recognized as $d = (d_2, d_1, d_3)$, notice that for $n \ge 2$, then we have

$$ \begin{aligned} \sigma(T) &= 2(d_2)^2 + d_1(d_1-1)^2 + d_2(d_3-d_2)^2 + 2 \\ &= d_1^3 - 2d_1^2 + d_1 + d_2^3 + 2d_2^2(1-d_3) + d_2d_3^2 + 2. \end{aligned} $$

**Case 3:** in this case we have the sequence recognized as $d = (d_1, d_3, d_2)$, then we notice This case is similar to Case 2, so that, for $n \ge 2$, we have:

$$ \begin{aligned} \sigma(T) &= d_1(d_1-1)^2 + d_2(d_3-1)^2 + d_1(d_2-d_1)^2 + 5 \\ &= 2d_1^3 - 2d_1^2(1+d_2) + d_1 + d_2d_3^2 - 2d_2d_3 + d_2 + 5. \end{aligned} $$

Therefore, from Case 1 and Case 2 we have:

$$ \sigma(T) = d_3^3 - 2d_2^2 + 2d_2d_3 - 5d_2d_3^2. $$

and from Case 1 and Case 2, we have:

$$ \sigma(T) = -d_1^3 + 2d_1^2d_2 + d_2^3 + d_3^3 - 5d_2d_3^2 + 2d_2d_3 - d_2 - 3. $$

from Case 2 and Case 3, we have:

$$ \sigma(T) = -d_1^3 + 2d_1^2d_2 + d_2^3 + 2d_2^2 - 2d_2^2d_3 + 2d_2d_3 - d_2 - 3. $$

Thus, we can clearly see that the first case is the maximum case and the second case is the minimum case for the sigma index, and we denote this by

$$ \sigma(T) = \begin{cases} \sigma_{\max}(T) = d_1^3 - 2d_1^2 + d_1 + d_2^3 + d_3^3 - 4d_2d_3^2 & \text{if } d_3 \ge 1, \\ \sigma_{\min}(T) = d_1^3 - 2d_1^2 + d_1 + d_2^3 + 2d_2^2(1-d_3) + d_2d_3^2 & \text{if } d_1 \ge 1. \end{cases} $$

As desire.

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

**Hypothesize 3.** Let $\tilde{d}$ be a degree sequence $\tilde{d} = (d_1, d_2, d_3, d_4)$ where $d_1 \ge d_2 \ge d_3 \ge d_4$. defined numbers as $(a, b, c, d)$ as $d > a \ge b \ge c$ we have:

$$ \text{irr}(G) = \sum_{i=1}^{n-1} (d_i - 1)^2 + (d-a) + (d-b) + (d-c) + (d-1)(d-3). $$

**Hypothesize 4.** Let $T$ be a tree of order $n > 0$ and a sequence $d = (d_1, d_2, d_3, d_4)$ where $d_4 \ge d_3 \ge d_2 \ge d_1$, then Sigma index is:

$$ \sigma(T) = \sum_{i=1}^{4} d_i^3 + 2 \sum_{i=1}^{4} d_i^2 + \sum_{i=1}^{4} d_i - 2 \sum_{i=1}^{3} d_i d_{i+1}. $$

if and only if the inequality holds the terms $d_1 > 0, d_2 = d_1+1, d_3 = d_2+1, d_4 = d_3 + 1$.
## 4 Analyse The Results For Topological Indices

In fact, both indices (Sigma Index and Albertson Index) have common preliminary factors based on the definition of each of them. in this section we will examine each index on two specific types of tree classes, the first type is normal trees and the second type is caterpillar trees, as we note that in Table 1 we show the Albertson Index on trees and caterpillar trees and the difference between both effects is clear as shown.

**Corollary 1.** For integer number $n \ge 3$, and a caterpillar tree $C(n, n)$, then we have:

$$ \mathrm{irr}(C) = n^3 + n^2 - 2n + 2. $$

*Proof.* Actually, for $n \in [3, 6]$ we have $\mathrm{irr}(C) = 13n^2 - 49n + 62$, but for $n \in [3, +\infty[$, this relationship will be corrected for some value not for all value, so that we have in Proposition 2 for $n \ge 3$, then $\mathrm{irr}(C) = m(m+1)n - 2m + 2$, but in our case $n = m$, then this relation become:

$$ \begin{aligned} \mathrm{irr}(C) &= m(m+1)n - 2m + 2 \\ &= n^2(n+1) - 2n + 2 \\ &= n^3 + n^2 - 2n + 2. \end{aligned} $$

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

**Corollary 2.** For caterpillar tree $C(n, m)$, with $n \in [3, 10]$, $m \in [3, 10]$, the we have:

$$ \left\{ \begin{array}{ll} \max(\mathrm{irr}(C), \sigma(C)) = \sigma(C) & \text{if } m \ge n, \\ \max(\mathrm{irr}(C), \sigma(C)) = \mathrm{irr}(C) & \text{if } n \ge 5, m = 3, \\ \max(\mathrm{irr}(C), \sigma(C)) = \mathrm{irr}(C) & \text{if } n \in \{7, 9\}, m \in \{4, 5\}. \end{array} \right. $$
<table><caption>**Table 1.** Compared Value of Sigma Index and Albertson Index on Caterpillar Tree.</caption><thead><tr><th>n</th><th>m</th><th>irr</th><th>σ</th><th>σ - irr</th><th>max(σ, irr)</th><th>n</th><th>m</th><th>irr</th><th>σ</th><th>σ - irr</th><th>max(σ, irr)</th></tr></thead><tbody><tr><td>3</td><td>3</td><td>32</td><td>55</td><td>23</td><td>55</td><td>5</td><td>3</td><td>56</td><td>55</td><td>-1</td><td>56</td></tr><tr><td>3</td><td>6</td><td>116</td><td>436</td><td>320</td><td>436</td><td>5</td><td>6</td><td>200</td><td>436</td><td>236</td><td>436</td></tr><tr><td>3</td><td>7</td><td>156</td><td>691</td><td>535</td><td>691</td><td>5</td><td>7</td><td>268</td><td>691</td><td>423</td><td>691</td></tr><tr><td>3</td><td>9</td><td>254</td><td>1465</td><td>1211</td><td>1465</td><td>5</td><td>9</td><td>434</td><td>1465</td><td>1031</td><td>1465</td></tr><tr><td>4</td><td>3</td><td>44</td><td>55</td><td>11</td><td>55</td><td>6</td><td>3</td><td>68</td><td>55</td><td>-13</td><td>68</td></tr><tr><td>4</td><td>4</td><td>74</td><td>130</td><td>56</td><td>130</td><td>6</td><td>4</td><td>114</td><td>130</td><td>16</td><td>130</td></tr><tr><td>4</td><td>7</td><td>212</td><td>691</td><td>479</td><td>691</td><td>6</td><td>7</td><td>324</td><td>691</td><td>367</td><td>691</td></tr><tr><td>4</td><td>9</td><td>344</td><td>1465</td><td>1121</td><td>1465</td><td>6</td><td>9</td><td>524</td><td>1465</td><td>941</td><td>1465</td></tr><tr><td>4</td><td>10</td><td>422</td><td>2008</td><td>1586</td><td>2008</td><td>6</td><td>10</td><td>642</td><td>2008</td><td>1366</td><td>2008</td></tr><tr><td>7</td><td>3</td><td>80</td><td>55</td><td>-25</td><td>80</td><td>9</td><td>3</td><td>104</td><td>55</td><td>-49</td><td>104</td></tr><tr><td>7</td><td>5</td><td>202</td><td>253</td><td>51</td><td>253</td><td>9</td><td>5</td><td>262</td><td>253</td><td>-9</td><td>262</td></tr><tr><td>7</td><td>7</td><td>380</td><td>691</td><td>311</td><td>691</td><td>9</td><td>7</td><td>492</td><td>691</td><td>199</td><td>691</td></tr><tr><td>7</td><td>8</td><td>490</td><td>1030</td><td>540</td><td>1030</td><td>9</td><td>8</td><td>634</td><td>1030</td><td>396</td><td>1030</td></tr><tr><td>7</td><td>9</td><td>614</td><td>1465</td><td>851</td><td>1465</td><td>9</td><td>9</td><td>794</td><td>1465</td><td>671</td><td>1465</td></tr><tr><td>7</td><td>10</td><td>752</td><td>2008</td><td>1256</td><td>2008</td><td>9</td><td>10</td><td>972</td><td>2008</td><td>1036</td><td>2008</td></tr><tr><td>8</td><td>3</td><td>92</td><td>55</td><td>-37</td><td>92</td><td>10</td><td>3</td><td>116</td><td>55</td><td>-61</td><td>116</td></tr><tr><td>8</td><td>5</td><td>232</td><td>253</td><td>21</td><td>253</td><td>10</td><td>5</td><td>292</td><td>253</td><td>-39</td><td>292</td></tr><tr><td>8</td><td>7</td><td>436</td><td>691</td><td>255</td><td>691</td><td>10</td><td>7</td><td>548</td><td>691</td><td>143</td><td>691</td></tr><tr><td>8</td><td>8</td><td>562</td><td>1030</td><td>468</td><td>1030</td><td>10</td><td>8</td><td>706</td><td>1030</td><td>324</td><td>1030</td></tr><tr><td>8</td><td>10</td><td>862</td><td>2008</td><td>1146</td><td>2008</td><td>10</td><td>10</td><td>1082</td><td>2008</td><td>926</td><td>2008</td></tr></tbody></table>

**Example 1.** let a sequence $d_1, d_2, d_3, d_4$; $d_1 \ge d_2 \ge d_3 \ge d_4$ and we will suppose sequences is: (10, 8, 3, 2), We will take 2 cases:

Case 1 (3, 10, 8, 2), in this case we have: $irr = 134$.

Case 2 (10, 3, 2, 8), in this case we have: $irr = 146$.

we suppose: $a = d_1, b = d_2, c = d_3, d = d_4$. So that we obtain on:

1. if $a = 10, b = 8, c = 3, d = 2$, in this case we have: $irr = 134, \sigma = 1036$.

2. if $a = 8, b = 10, c = 3, d = 2$, in this case we have: $irr = 134, \sigma = 1048$.

3. if $a = 3, b = 10, c = 8, d = 2$, in this case we have: $irr = 144, \sigma = 1148$.

4. if $a = 2, b = 10, c = 8, d = 3$, in this case we have: $irr = 146, \sigma = 1156$.

<table><thead><tr><th colspan="2">irr</th><th colspan="2">σ</th></tr><tr><th>max</th><th>min</th><th>max</th><th>min</th></tr></thead><tbody><tr><td>146</td><td>134</td><td>1156</td><td>1036</td></tr></tbody></table>

**Example 2.** let a sequence $d_1, d_2, d_3, d_4$; $d_1 \ge d_2 \ge d_3 \ge d_4$ and we will suppose sequences is: (8, 5, 3, 2), We will take 4 cases as:

Case 1 (8, 5, 3, 2), in this case we have: $irr = 70$.
else:

print("The list is NOT sorted from largest to smallest.")

# 5 Conclusion

Topological indices are very important in graphs, especially on trees, and through this paper we presented both the sigma index and the Albertson index. We studied these indices on trees, including caterpillar trees, and analysed these results by creating a table to demonstrate these results.

# Acknowledgments

I would like to extend my deepest gratitude to Prof. Alexei Kanel-Belov. Also, I grateful for Dr. Duaa Abdullah for positive feedback.

# References

[1] L. Collatz and U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg 21:63-77 (1957).

[2] M. O. Albertson, The irregularity of graph, Ars Comb. 46 (1997) 2015-25.

[3] Harary, F., Graph Theory, 1969, Addison-Wesley Publishing.

[4] Wai-Kai Chen, Applied Graph Theory, 1971, North - Hollywood and Publishing Company - Amsterdam -London.

[5] G. H. Fath Tabar, I. Gutman, R. Nasiri, Extremely Irregular Trees, Bulletin T.CXLV de l'Académie serbe des sciences et des arts – 2013 Classe des Sciences mathématiques et naturelles Sciences mathématiques, No 38.

[6] Dorjsembe, S, Buyantogtokh, L, Das, KC, Horoldagva, B, Graphs with maximum irregularity, Computational and Applied Mathematics, volume 41, issue 6, 2022, https://doi.org/10.1007/s40314-022-01967-3.

[7] Voloshin, V. I. (2009). Introduction to Graph and Hypergraph Theory. Nova Science Publishers. https://books.google.ru/books?id=-4rrmgEACAAJ.
[8] I. Gutman, P. Hansen, H. Melót, Variable neighborhood search for extremal graphs 10. Comparison of irregularity indices for chemical trees, J. Chem. Inf. Model. 45 (2005) 222–230.

[9] H. Abdo, S. Brandt, D. Dimitrov, The total irregularity of a graph, Discrete Math. Theor. Comput. Sci. 16 (2014a) 201–206.

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

[11] H. Abdo, D. Dimitrov, I. Gutman, Graph irregularity and its measures, Applied Mathematics and Computation, Volume 357, 2019, Pages 317–324, https://doi.org/10.1016/j.amc.2019.04.013.

[12] I. Gutman, B. Russcić, N. Trinajstić, C. F. Wilcox, Graph theory and molecular orbitals. XII Acyclic polyens, J. Chem. Phys. 62 (1975) 3399–3405.

[13] Zhang, P., Wang, X. Several Topological Indices of Random Caterpillars. Methodol Comput Appl Probab 24, 1773–1789 (2022). https://doi.org/10.1007/s11009-021-09895-1.

[14] I. Gutman, M. Togan, A. Yurttas, A.S. Cevik, I.N. Cangul, Inverse problem for sigma index, MATCH Commun. Math. Comput. Chem. 79 (2018) 491–508.

[15] H. Abdo, D. Dimitrov, I. Gutman, Graphs with maximal $\sigma$ irregularity, Elsevier B.V, 2018, doi:10.1016/j.dam.2018.05.013.

[16] Ghalavand, A., Ashrafi, A., R., Ordering of c-cyclic graphs with respect to total irregularity, Journal of Applied Mathematics and Computing, Volume 63, Issue , 2020, Pages 707–715, https://doi.org/10.1007/s12190-020-01335-6.

[17] Filipovski, S., Dimitrov, D., Knor, M., & Škrekovski, R. (2024). Some results on $\sigma_t$-irregularity. arXiv preprint arXiv:2411.04881.

[18] Darko D., Dragan S., On the t-irregularity and the inverse irregularity problem, Applied Mathematics and Computation, Volume 441, 2023, 127709, https://doi.org/10.1016/j.amc.2022.127709.
[19] F. K. Bell, A note on the irregularity of graphs, Lin. Algebra Appl. 161 (1992) 45–54.

[20] Marjan, Matejic., B., Mitin., Emina, I., Milovanovic., Igor, Z., Milovanovi. (2019). On Alberson irregularity measure of graphs. 11(2):97-106, doi: 10.5937/SPSUNP1902097M.

[21] A. Sekar, K. Prabhavathi and M. Arockia Ranjithkumar, Sigma Index in Some Special Graphs, Advances and Applications in Mathematical Sciences, Volume 21, Issue 7, May 2022.