On graph irregularity indices with particular regard to degree deviation

Abstract

Let $G=(V,E)$, $V=\{v_1,v_2,\ldots,v_n\}$, be a simple connected
graph of order $n$ and size $m$, with vertex degree sequence
$d_1\ge d_2\ge\cdots \ge d_{n}$. A graph $G$ is said to be regular if $d_1=d_2=\cdots =d_n$. Otherwise it is irregular. In many applications and problems it is important to know how irregular a given graph is.
A quantity called degree deviation $S(G)=\sum_{i=1}^n\left|d_i-\frac{2m}{n}\right|$ can be used as an irregularity measure. Some new lower bounds for $S(G)$ are obtained. A simple formula for computing $S(G)$ for connected bidegreed graphs is derived also. Besides, two novel irregularity measures are introduced.