THE IRREGULARITY COST OF A GRAPH

A multigraph H is irregular if no two of its nodes have the same degre e. It has been shown that a graph is the underlying graph of some irre gular multigraph if and only if it has at most one trivial component a nd no components of order 2. We define the irregularity cost of such a graph G to be the minimum number of additional edges in an irregular multigraph having G as its underlying graph. We determine the irregula rity cost of certain regular graphs, including those with a Hamiltonia n path. We also determine the irregularity cost of paths and wheels, a s examples of nearly regular graphs. At the opposite extreme, we deter mine the irregularity cost of graphs with exactly one pair of nodes of equal degree. As expected, their cost is relatively low.