Irregularity and Near Star Graphs

Abstract

The (Albertson) irregularity of a graph G is irr ( G ) = ∑︁ | d ( u ) − d ( v ) | , where the sum is over all edges of G . In 2005, Hansen and M´elot proved an upper bound on the irregularity of a graph on n vertices and m edges that is attained for all feasible values, and characterized the extremal graphs. We give a much shorter proof of this result, and discuss some of its implications. Denoting the extremal graphs as near k -star graphs, we show that they sometimes occur as extremal graphs for related problems on sigma irregularity and first Zagreb index.