The Irregularity of a Graph

Abstract

The imbalance of edge $(x,y)=|\mathrm{deg}(x)–\mathrm{deg}(y)|$.The sum of all edge imbalances in a graph is called its irregularity.
We determine the maximum irregularity of various classes of graphs.For example, the irregularity of an arbitrary graph with $n$ vertices is less than $\frac{4n^3}{27}$, and this bound is tight.