The Irregularity Cost of a Graph

AbstractA multigraph H is irregular if no two of its nodes have the same degree. It has been shown that a graph is the underlying graph of some irregular multigraph if and only if it has at most one trivial component and 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 irregularity cost of certain regular graphs, including those with a Hamiltonian path. We also determine the irregularity cost of paths and wheels, as examples of nearly regular graphs. At the opposite extreme, we determine the irregularity cost of graphs with exactly one pair of nodes of equal degree. As expected, their cost is relatively low