ALCOMFT-TR-01-129

Hans L. Bodlaender, Richard B. Tan and Jan van Leeuwen
Finding a \Delta-regular Supergraph of Minimum Order
Utrecht. Work package 2. May 2001.

Abstract: Akiyama, Era and Harary [AkiyamaEH83] proved that every graph of maximum degree \Delta is a subgraph of a \Delta-regular graph that has at most \Delta+2 additional vertices. We show that, given a graph of maximum degree \Delta, a \Delta-regular supergraph of it of minimum order can be computed in O(min {\Delta^1.5 |V|^2.5, \Delta⁶ + \Delta |V|}) time.

Postscript file: ALCOMFT-TR-01-129.ps.gz (81 kb).