# Irregularity Measure of Graphs

Authors: Ali Ghalavand; Ivan Gutman; Mostafa Tavakoli
Journal: Journal of Mathematics
 (2023)

---

## Abstract

A simple graphG is said to be regular if its vertices have the same number of neighbors. Otherwise, G is nonregular. So far, various formulas, such as the Albertson index, total Albertson index, and degree deviation, have been introduced to quantify the irregularity of a graph. In this paper, we present sharp lower bounds for these indices in terms of the order, size, maximum degree, minimum degree, and forgotten and Zagreb indices of the underlying graph. We also prove that if G has the minimum value of degree deviation, among all nonregular n,m-graphs, then ΔG−δG=1.


---

## Body

## 1. Introduction

LetG be a graph and let v be a vertex of G. We say that G is an n,m-graph if its order and size are n and m, respectively. As usual, we use dGv to denote the degree of the vertex v. Moreover, Δ and δ are used to denote the maximum and minimum vertex degrees, respectively.In [1], the first Zagreb M1 and the second Zagreb indices M2 were introduced as follows:(1)M1G=∑uv∈EGdGu+dGv=∑v∈VGdGv2,M2G=∑uv∈EGdGudGv.The forgotten topological index,FG, is defined as follows [2]:(2)FG=∑uv∈EGdGu2+dGv2=∑v∈VGdGv3.A graphG is said to be r1,…,rk-regular if ∪v∈VGdGv=r1,…,rk. If r1=⋯=rk=r, then G is called r-regular or regular for brevity; otherwise, G is nonregular. Until now, various formulas have been introduced to quantify the irregularity of a graph. We refer to the interesting readers to consult the recently published book of Ali et al. [3] for more information on this topic. Albertson in [4] introduced the following formula as an irregularity measure of a connected graph G:(3)irrG=∑uv∈EGdGu−dGv.Today, this parameter is known as the Albertson index and is denoted byirrG. A few years later, Nikiforov presented the degree deviation S as follows [5]:(4)SG=∑v∈VGdGv−2mn.Moreover, Abdo et al. in [6] expanded the Albertson index as follows:(5)irrtG=∑u,v⊆VGdGu−dGv.They called it as the total irregularity index and denoted it byirrt. We encourage the interested reader to study references [7–16] for more details on these irregularity measures. Although some graphs with equal irregularity indices are presented in [17], there are some comparisons between these parameters in [18], which may imply the unreliability of them. In [19], relation between the chromatic number and irregularity measures was investigated. In [20–22], some bounds on irr of graphs were given. In the next section, we obtain further sharp lower bounds for (total) Albertson indices and degree deviation of a graph in terms of its order, size, maximum degree, minimum degree, forgotten, and Zagreb indices. Finally, we show that if G has the minimum value of S among all nonregular n,m-graphs, then ΔG−δG=1.


## 2. Main Results

In this section, we give lower bounds for (total) Albertson indices and the degree deviation of a graphG. We end this section with a result related to the minimality of S.Theorem 1.
LetG be a nonregular n,m-graph. Then,(6)irrtG≥nM1G−4m2Δ−δ,and the equality holds if and only if G is Δ,δ-regular.Proof.
For eachu,v⊆VG,(7)dGu−dGv≤Δ−δ,and the equality holds if and only if dGv,dGu=Δ,δ. Then,(8)∑u,v⊆VGdGu−dGv2≤∑u,v⊆VGΔ−δdGu−dGv=Δ−δirrtG,and the equality holds if and only if dGu,dGv:u,v⊆VG=Δ,δ, and the this relation holds if and only if G is Δ,δ-regular. On the other hand,(9)∑u,v⊆VGdGu−dGv2=∑u,v⊆VGdGu2+dGv2−2dGudGv=∑u∈V∑v∈VdGu2−dGudGv=∑u∈VndGu2−2mdGu=nM1G−4m2.
Therefore, by relation (8), we conclude that(10)irrtG≥nM1G−4m2Δ−δ,and the equality holds if and only if G is Δ,δ-regular.Corollary 1.
IfG is a nonregular n,m-graph, then(11)irrtG≥2mn2Δ−1+n2ΔΔ−1−4m2Δ−δ,and the equality holds if and only if G is Δ,Δ−1-regular. Also,(12)irrtG≥2mn2δ+1−n2δδ+1−4m2Δ−δ,and the equality holds if and only if G is δ+1,δ-regular.Proof.
For eachv∈VG, Δ≥dGv≥δ. This yields that for each v∈VG, we have(i)
dGv−ΔdGv−Δ+1≥0 and the equality holds if and only if dGv∈Δ−1,Δ(ii)
dGv−δdGv−δ−1≥0 and the equality holds if and only if dGv∈δ,δ+1.
From (i), we get(13)∑v∈VGdGv−ΔdGv−Δ+1≥0,and the equality holds if and only if G is Δ,Δ−1-regular. Also, according to (ii), we can write(14)∑v∈VGdGv−δdGv−δ−1≥0,and the equality holds if and only if G is δ+1,δ-regular. Due to the abovementioned argument, we can easily conclude that(15)M1G≥2m2Δ−1−nΔΔ−1,and the equality holds if and only if G is Δ,Δ−1-regular. We can also easily drive that(16)M1G≥2m2δ+1−nδδ+1,and the equality holds if and only if G is δ+1,δ-regular. Using Theorem 1,(17)irrtG≥2mn2Δ−1−n2ΔΔ−1−4m2Δ−δ,and the equality holds if and only if G is Δ,Δ−1-regular. Also,(18)irrtG≥2mn2δ+1−n2δδ+1−4m2Δ−δ,and the equality holds if and only if G is δ+1,δ-regular.Theorem 2.
LetG be a connected nonregular n,m-graph. Then,(19)irrG≥FG−2M2GΔ−δ,and the equality holds if and only if G is Δ,δ-regular.Proof.
For eachuv∈EG, dGu−dGv≤Δ−δ and the equality holds if and only if dGu,dGv=Δ,δ. This implies that(20)∑uv∈EGdGu−dGv2≤∑uv∈EGΔ−δdGu−dGv=Δ−δirrG,and the equality holds if and only if dGu,dGv:uv∈EG=Δ,δ. Since G is connected, then we can say that the equality holds if and only if G is Δ,δ-regular. On the other hand,(21)∑uv∈EGdGu−dGv2=∑uv∈EGdGu2+dGv2−2dGudGv=FG−2M2G.
Then, using equation (20), we have(22)irrG≥FG−2M2GΔ−δ,and the equality holds if and only if G is Δ,δ-regular.Theorem 3.
IfG is a nonregular n,m-graph, then(23)SG≥2nM1G−8m2nΔ−δ,and the equality holds if and only if G is Δ,δ-regular or Δ,2m/n,δ-regular.Proof.
LetVG=v1,v2,…,vn. Let also that ai=dGvi−2m/n for i=1,2,…,n. Then, it is evident that(24)∑i=1nai=∑i=1ndGvi−2mn=2m−n2mn=0.
Then, the relation follows:(25)∑i=1nai2=12∑i=1n2ai−Δ−δ+4mnai≤12∑i=1n2ai−Δ−δ+4mnai,and the equality holds if and only if 2ai−Δ−δ+4m/n and ai the same sign. On the other hand, for i=1,2,…,n, we have(26)δ−2mn≤ai≤Δ−2mn,and the left equality holds if and only if dGvi=δ and the right equality holds if and only if dGvi=Δ. Thus,(27)δ−Δ≤2ai−Δ−δ+4mn≤Δ−δ,and the left equality holds if and only if dGvi=δ and the right equality holds if and only if dGvi=Δ. Consequently, 2ai−Δ−δ+4m/n≤Δ−δ and the equality holds if and only if dGvi∈Δ,δ. Then,(28)2ai−Δ−δ+4mnai≤Δ−δai,and the equality holds if and only if dGvi∈Δ,2m/n,δ. Thus, by relation (25), we arrive at the relation:(29)∑i=1nai2≤12∑i=1nΔ−δai=12Δ−δ∑i=1ndGvi−2mn=12Δ−δSG.
Moreover,∑i=1ndGvi−2m/n2=1/2Δ−δSG if and only if the equalities hold in relations (20) and (28) for i=1,2,…,n, and these are satisfied if and only if G is Δ,δ-regular or Δ,2m/n,δ-regular. On the other hand,(30)∑i=1ndGvi−2mn2=∑i=1ndGvi2+4m2n2−4mndGvi=M1G−4m2n.
By using relation (30), SG≥2nM1G−8m2/nΔ−δ and the equality holds if and only if G is Δ,δ-regular or Δ,2m/n,δ-regular.
By a similar argument applied in Corollary1, we can obtain the next result.Corollary 2.
LetG be a nonregular n,m-graph. Then,(31)SG≥4nm2Δ−1−2n2ΔΔ−1−8m2nΔ−δ,and the equality holds if and only if G is Δ,Δ−1-regular. Also,(32)SG≥4nm2δ+1−2n2δδ+1−8m2nΔ−δ,and the equality holds if and only if G is δ+1,δ-regular.Lemma 1.
LetG be an n,m-graph. If ΔG−δG≥2, then at most one of the relations ΔG−1<2m/n and 2m/n<δG+1 holds.Proof.
Assume, to the contrary, that the both of relationsΔG−1<2m/n and 2m/n<δG+1 hold. Thus, ΔG−δG<2, which leads to a contradiction because ΔG−δG≥2.Theorem 4.
LetG be an n,m-graph. If ΔG−δG≥2, then there exists an n,m-graph G1 such that G≇G1, ΔG−δG≥ΔG1−δG1, and SG>SG1.Proof.
Letu and v be two vertices of G such that dGu=ΔG, dGv=δG and dGu−dGv≥2. Then, NGu/NGv≠∅, and consequently, we suppose x∈NGu/NGv and define G1=G−xu+xv. Thus, G1 is an n,m-graph such that G1≇G, ΔG≥ΔG1, and δG1≥δG. Then, ΔG−δG≥ΔG1−δG1. Now, we consider three cases by Lemma 1 for computing SG−SG1:(i)
ΔG−1≥2m/n and 2m/n≥δG+1. In this case, by the definition of S, we have(33)SG−SG1=ΔG−2mn+2mn−δG−ΔG−1−2mn−2mn−δG−1=2.(ii)
2m/n>ΔG−1 and 2m/n≥δG+1. In this case, we have(34)SG−SG1=ΔG−2mn+2mn−δG−2mn−ΔG+1−2mn−δG−1=2ΔG−2mn>0.(iii)
2m/n≤ΔG−1 and 2m/n<δG+1. Then,(35)SG−SG1=ΔG−2mn+2mn−δG−ΔG−1−2mn−δG+1−2mn=22mn−δ>0.
Using cases (i–iii) and Lemma1, we reach to SG>SG1, which completes the proof.Corollary 3.
IfG has the minimum value of S among all nonregular n,m-graphs, then ΔG−δG=1.



---

*Source: 4891183-2023-03-20.xml*