Inducing regulation of any digraphs

AbstractFor a given structure D (digraph, multidigraph, or pseudodigraph) and an integer r large enough, a smallest inducing r-regularization of D is constructed. This regularization is an r-regular superstructure of the smallest possible order with bounded arc multiplicity, and containing D as an induced substructure. The sharp upper bound on the number, ρ, of necessary new vertices among such superstructures for n-vertex general digraphs D is determined, ρ being called the inducing regulation number of D. For Δ̃(D) being the maximum among semi-degrees in D, simple n-vertex digraphs D with largest possible ρ are characterized if either r≥Δ̃(D) or r=Δ̃(D) (where the case r=Δ̃ is not a trivial subcase of r≥Δ̃)