Sigma index in Trees with Given Degree Sequences

Jasem Hamoud¹, Artem Kurnosov²

¹,² Moscow Institute of Physics and Technology (National Research University).

# 1 Introduction.

The sigma index in graph theory refers to a measure of the degree differences between vertices in a graph. The goal is to determine the graphs that have the maximum sigma index within certain classes of graphs. Abdo, Dimitrov, and Gutman characterized the graphs with the greatest sigma index among all connected graphs of a fixed order in [1] as:

1. $\sigma(G) = \text{irr}(G) = \sum_{uv \in E(G)} |d_G(u) - d_G(v)| = 0$, if and only if G is regular, then that's mean: $d_G(u) = d_G(v); \forall uv \in E(G)$;

2. $\sigma(G) = \text{irr}(G) = \sum_{uv \in E(G)} |d_G(u) - d_G(v)| > 0$, if and only if G is stepwise regular, then that's mean: $d_G(u) > d_G(v); \forall uv \in E(G) \text{ord}_G(v) > d_G(u); \forall uv \in E(G)$.

Also, Gutman, Togan, Yurttas, Cevik, Cangul introduced sigma index $\sigma$ in graph in [2] as:

$$ \sigma = \sum_{uv \in E(G)} (d_G(u) - d_G(v))^2. $$

# 2 Main Result.

**Hypothesize 2.1.** Let be a sequence $\tilde{d} = (d_1, d_2, d_3)$; $d_1 \ge d_2 \ge d_3$ of order $n$ where $n \le 4$ we have: $\text{irr}_{\text{max}} - \text{irr}_{\text{min}} = 2(d_2 - d_3)$ that is mean: $d(\text{irr}_{\text{max}}, \text{irr}_{\text{min}}) = 2(d_2 - d_3)$ if $d_2 = d_3 \implies d_G(\text{irr}_{\text{max}}, \text{irr}_{\text{min}}) = 2$, where The distance $d_G(u, v)$ between two vertices $u, v$ of G is the length of one of the shortest $(u, v)$-path in G

**Lemma 2.2.** A sequence of positive integers $d_1, d_2, d_3$; $d_1 \ge d_2 \ge d_3$ and defined numbers : $a \ge b \ge c$. so that, sigma index defined as:

$$ \text{irr} = \begin{cases} \text{irr}_{\text{max}} = (a-1)^2 + (b-1)^2 + (c-1)(c-2)(a-c)(b-c) \\ \text{irr}_{\text{min}} = (a-1)^2 + (c-1)^2 + (b-1)(b-2) + (a-c) \end{cases} $$

we have 3 cases as:

<table><caption>Table 1: positive integer $d_1, d_2, d_3$.</caption><thead><tr><th>case 1</th><th>case 2</th><th>case 3</th></tr></thead><tbody><tr><td><img src="image_1.png" alt="A tree with a root at $d_3$ and leaves at $d_1$ and $d_2$"></td><td><img src="image_2.png" alt="A tree with a root at $d_3$ and leaves at $d_1$ and $d_2$"></td><td><img src="image_3.png" alt="A tree with a root at $d_1$ and leaves at $d_3$ and $d_2$"></td></tr></tbody></table>

we have for Albertson Index irregularity : case1 = case2 $\le$ case3.
**Example 2.3.** let a sequence $d_1, d_2, d_3;d_1 \ge d_2 \ge d_3$ and we will suppose sequences is: (4, 3, 2) we have 3 cases as:

<table><caption>Table 2: Albertson Index and Sigma Index for a sequence $d_1, d_2, d_3;d_1 \ge d_2 \ge d_3$.</caption><thead><tr><th>case 1</th><th>case 2</th><th>case 3</th></tr></thead><tbody><tr><td>3<br>4<br>irr = 14<br>σ = 34</td><td>4<br>3<br>irr = 14<br>σ = 32</td><td>4<br>3<br>irr = 16<br>σ = 40</td></tr></tbody></table>

**Example 2.4.** 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, 4, 2) we have 12 options, for example we take:

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

Let we take:

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

We can discuss many cases according to the following:

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

if $d = 2$ we have:

$$49 + 16 + 4 + 2 + 9 = 80 \Rightarrow irr = 80$$

$$343 + 16 + 27 + 84 = 470 \Rightarrow \sigma = 470$$

From this case we can formed many methods to obtain on maximum value, we will take for example $d = 4$ we have:

$$3 + 1 + 16 + 49 + 2 + 1 + 4 = 76 \Rightarrow irr = 76$$

$$9 + 22 + 343 + 64438 \Rightarrow \sigma = 438$$
We can formulate that as:

$$irr = (a - 1)^2 + (b - 1)^2 + (c - 1)^2 + (d - a) + (d - b) + (d - c) + (d - 1)(d - 3),$$

$$\text{if } (d = 8, a = 5, b = 4, c = 2) \Rightarrow \text{irr} = 74$$

If $d = 5$ we have:

$$8 + 10 + 49 + 10 = 74 \Rightarrow \text{irr} = 74$$

$$32 + 19 + 343 + 28 = 422 \Rightarrow \sigma = 422$$

If $d = 8$ we have:

$$35 + 10 + 29 = 74 \Rightarrow \text{irr} = 74$$

$$64 + 27 + 36 + 26 + 245 = 398 \Rightarrow \sigma = 398$$

we will get on:

<table><thead><tr><td>sequence of d</td><td>irr</td><td>σ</td></tr></thead><tbody><tr><td>2</td><td>80</td><td>470</td></tr><tr><td>4</td><td>76</td><td>438</td></tr><tr><td>5</td><td>74</td><td>422</td></tr><tr><td>8</td><td>74</td><td>398</td></tr></tbody></table>

In the end we get on:

<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>80</td><td>74</td><td>470</td><td>398</td></tr></tbody></table>

## References

[1] Hosam, A., Darko, D., Ivan G., 2018, Graphs with maximal $\sigma$ irregularity, Elsevier B.V, doi.org/10.1016/j.dam.2018.05.013.

[2] 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.