Bounds and Computation of Irregularity of a Graph

arXiv1207.4804MaRDI QIDQ6234517FDOQ6234517

Authors: Hosam Abdo, Nathann Cohen, Darko Dimitrov 

Publication date: 19 July 2012

Abstract: Albertson has defined the irregularity of a simple undirected graph $G=(V,E)$ as $irr(G)=su{m}_{uvinE}|d_G(u)-d_G(v)|,$ where $d_G(u)$ denotes the degree of a vertex $uinV$. Recently, this graph invariant gained interest in the chemical graph theory, where it occured in some bounds on the first and the second Zagreb index, and was named the third Zagreb index Fath-Tabar. 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 Albertson, we show that for general graphs with $n$ vertices the upper bound $lfloorfracn3floorlceilfrac2n3ceil(lceilfrac2n3ceil-1)$ is sharp. Next, we determine $k$-cyclic graphs with maximal irregularity. We also present some bounds on the maximal/minimal irregularity of graphs with fixed minimal and/or maximal vertex degrees, and consider an approximate computation of the irregularity of a graph.

This page was built for publication: Bounds and Computation of Irregularity of a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6234517)