Highly irregular graphs with extreme numbers of edges (Q1356711)

A graph is highly irregular if the neighbours of each vertex have distinct degrees. The authors determine the largest number of edges of a highly irregular graph with an odd number of vertices (the same problem had been solved in 1987 for graphs with an even number of vertices by Alavi, Chartrand, Chung, Erdös, Graham and Oellermann). The authors also determine the smallest number of edges in a highly irregular graph of any given order.