Note on Irregular Graphs

Ivan Gutman ; Tamás Réti

Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 43 (2018) no. 1.

Résumé

Let $G$ be a graph with vertex set $\mathbf V(G)$ and edge set $\mathbf E(G)$. For $v \in \mathbf V(G)$, by $d_G(v)$ is denoted the degree of the vertex $v$. A graph in which not all vertices have equal degrees is said to be irregular. Different quantitative measures of irregularity have been proposed, of which the Albertson index $irr(G) = \sum_{uv \in \mathbf E(G)} |d_G(u)-d_G(v)|$ is the most popular. We compare $irr(G)$ with the recently introduced sigma-index $\sigma(G) = \sum_{uv \in \mathbf E(G)} [d_G(u)-d_G(v)]^2$ and show that in the general case these are incomparable. Graphs in which $|d_G(u)-d_G(v)|=1$ holds for all $uv \in \mathbf E(G)$ are called stepwise irregular $($SI$)$. Several methods for constructing SI graphs are described.