On the irregularity of bipartite graphs (Q878643)

Let \(G=(V,E)\) be a finite simple graph. For \(u\in V\), let \(d(u)\) denote the valence of \(u\). For any edge \(e=uv\in E\), the imbalance of \(e\) is \(| d(u)-d(v)| \). The irregularity of \(G\), denoted \(\text{{irr}}(G)\), is the sum of the imbalances of the edges of \(G\). These notions are due to \textit{M. O. Albertson} [Ars Comb. 46, 219--225 (1997; Zbl 0933.05073)]. This paper provides formal proofs of some of Albertson's unproven claims. The authors determine first the structure of graphs with maximum irregularity when the cardinalities of the partite sets and the number of edges are given and then when just the cardinalities of the partite sets are given. In particular, it is shown that if both partite sets have cardinality \(m\), then \(\text{{irr}}(G)\leq3m^3/27\), and this bound is best possible. If the partite sets have cardinalities \(m\) and \(n\), respectively, with \(m\geq2n\), then \(\text{{irr}}(G)\leq\text{{irr}}(K_{m,n})=mn(m-n)\).