Inducing Regularization of Graphs, Multigraphs and Pseudographs

Abstract

For a given structure (graph, multigraph, or pseudograph) \(G\) and an integer \(r \geq \Delta(G)\), a smallest inducing \(r\)-regularization of \(G\) (which is an \(r\)-regular superstructure of the smallest possible order, with bounded edge multiplicities, and containing \(G\) as an induced substructure) is constructed.