Finding a Δ-regular supergraph of minimum order Original Research Article

Akiyama et al. (Elem. Math. 83 (1983) 15) proved that every graph of maximum degree Δ is a subgraph of a Δ-regular graph that has at most Δ+2 additional vertices. We show that, given a graph of maximum degree Δ, a Δ-regular supergraph of it of minimum order can be computed in image time.