## Abstract

The imbalance of an edge uv in a graph G is defined as | d (u) - d (v) |, where d (u) denotes the degree of u. The irregularity of G, denoted irr (G), is the sum of the edge imbalances taken over all edges in G. We determine the structure of bipartite graphs having maximum possible irregularity with given cardinalities of the partite sets and given number of edges. We then derive a corresponding result for bipartite graphs with given cardinalities of the partite sets and determine an upper bound on the irregularity of these graphs. In particular, we show that if G is a bipartite graph of order n with partite sets of equal cardinalities, then irr (G) ≤ n^{3} / 27, while if G is a bipartite graph with partite sets of cardinalities n_{1} and n_{2}, where n_{1} ≥ 2 n_{2}, then irr (G) ≤ irr (K_{n1, n2}).

Original language | English |
---|---|

Pages (from-to) | 1467-1472 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 307 |

Issue number | 11-12 |

DOIs | |

Publication status | Published - 28 May 2007 |

Externally published | Yes |

## Keywords

- Bipartite
- Edge imbalance
- Graph irregularity

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics