On the irregularity of bipartite graphs (Q878643)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the irregularity of bipartite graphs |
scientific article |
Statements
On the irregularity of bipartite graphs (English)
0 references
26 April 2007
0 references
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)\).
0 references
bipartite
0 references
edge imbalance
0 references
graph irregularity
0 references