Note on irregular graphs

Abstract

Let G be a graph with vertex set V(G) and edge set E(G). For v ∈ V(G), by dG(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) = Σuv∈E(G) |dG(u) − dG(v)| is the most popular. We compare irr(G) with the recently introduced sigma-index σ(G) = Σuv∈E(G)[dG(u) − dG(v)]2 and show that in the general case these are incomparable. Graphs in which |dG(u)−dG(v)| = 1 holds for all uv ∈ E(G) are called stepwise irregular (SI). Severalmethods for constructing SI graphs are described.