The irregularity cost of a graph (Q1388975)

A multigraph is called irregular if no two of its nodes have the same degree. If a graph \(G\) has at most one trivial component and no component isomorphic to \(K_2\), then there exists a multigraph \(H\) having \(G\) as underlying graph. We call such a multigraph \(H\) an irregular \(G\)-multigraph. For such a graph \(G\), the irregularity cost \(\text{ic}(G)\) is the minimum number of additional edges in an irregular \(G\)-multigraph. As an example, \(\text{ic} (K_{1,r})={r\choose 2}\). Theorem 1. Let \(G\) be a regular graph of order \(n\geq 4\) that contains a path of \(n-1\) nodes. Then \(\text{ic}(G)=(n^2-n)/4\) if \(n\equiv 0,1 \pmod 4\), \((n^2-n+2)/4\) if \(n\equiv 2,3 \pmod 4\). Theorem 2. For \(n\geq 4\) the irregularity cost of the path of order \(n\) is \(\text{ic}(P_n)= (n^2-3n+4)/4\) if \(n\equiv 0,3 \pmod 4\), \((n^2-3n+6)/4\) if \(n\equiv 1,2 \pmod 4\).