Let G be a graph. The irregularity index of G, denoted by t (G), is the number of distinct values in the degree sequence of G. For any graphG, t (G) ≤ ?(G), where ?(G) is the maximum degree. If t (G) = ?(G), then G is called maximally irregular. In this paper, we give a tight upper bound on the size of maximally irregular graphs, and prove the conjecture proposed in [6] on the size of maximally irregular triangle-free graphs. Extremal graphs are also characterized.
展开▼
