Note on irregular graphs
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.
Keywords:degree (of vertex) / irregularity (of graph) / stepwise irregular graph / Albertson index / σ index
Source:Bulletin T.CLI de l’Académie serbe des sciences et des arts, 2018, 5-16
- Beograd : Académie Serbe des sciences et des arts
- Bulletin de l'Académie serbe des sciences. Classe des sciences mathématiques et naturelles. Sciences mathématiques. 43, 151 (2018).