The Regulation Number of a Graph


Jin Akiyama, Frank Harary


The regulation number $r(G)$ of a graph $G$ with maximum degree $d$ is defined as the smallest number of new points in a $d$-regular supergraph. It is shown that for $d\geq3$, every possible value of $r(G)$ between zero and the maximum established by Akiyama, Era and Harary, namely, $d$(mod 2)$+1+d$, is realized by some graph. Also, a characterization is given for $G$ to have $r(G)=n$.