Note on Irregular Graphs
Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles, Tome 43 (2018) no. 1
Citer cet article
Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts
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.