PUBLICATIONS DE L'INSTITUT MATHÉMATIQUE (BEOGRAD) (N.S.)
Vol. 34(48), pp. 3--5 (1983)
THE REGULATION NUMBER OF A GRAPH
Jin Akiyama, Frank HararyNippon Ika University Kawasaki, Japan and University of Michigen Ann Arbor, USA
Abstract: 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$.
Classification (MSC2000): 03B50
Full text of the article:
Electronic fulltext finalized on: 3 Nov 2001. This page was last modified: 16 Nov 2001.
© 2001 Mathematical Institute of the Serbian Academy of Science and Arts