Graphs With Maximal Irregularity

Hosam Abdo, Nathann Cohen, Darko Dimitrov

Albertson [3] has defined the \emph{irregularity} of a simple undirected graph $G=(V,E)$ as irr$(G)=\sum_{uv\in E}|d_G(u)-d_G(v)|$, where $d_G(u)$ denotes the degree of a vertex $u\in V$. Recently, this graph invariant gained interest in the chemical graph theory, where it occurred in some bounds on the first and the second Zagreb index, and was named the \emph{third Zagreb index} [12]. For general graphs with $n$ vertices, Albertson has obtained an asymptotically tight upper bound on the irregularity of $4n^3/27$. Here, by exploiting a different approach than in [3], we show that for general graphs with $n$ vertices the upper bound $\lfloor\frac n3\rfloor\lceil\frac{2n}3\rceil\big(\lceil\frac{2n}3\rceil-1\big)$ is sharp. We also present lower bounds on the maximal irregularity of graphs with fixed minimal and/or maximal vertex degrees, and consider an approximate computation of the irregularity of a graph.