Highly irregular bipartite graphs (Q1917732)

A connected graph is called highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper an upper bound for the size of a highly irregular graph of order \(2n + 1\) is given. This bound is better than the bound given by Alavi et al. Furthermore all highly irregular graphs whose complements are also highly irregular are characterized, and highly irregular bipartite graphs of orders \(n \neq 3, 5, 7\) are constructed. In addition, it is shown that there is a highly irregular bipartite graph with bipartite size \((n,n)\) and with maximum degree \(m\) for \(n \geq m \geq 3\).