Inducing regulation of any digraphs |
| |
Authors: | Joanna Górska Zdzis?aw Skupień |
| |
Institution: | Faculty of Applied Mathematics, AGH University of Science and Technology, al. Mickiewicza 30, 30-059 Kraków, Poland |
| |
Abstract: | For 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 being the maximum among semi-degrees in D, simple n-vertex digraphs D with largest possible ρ are characterized if either or (where the case is not a trivial subcase of ). |
| |
Keywords: | Regular digraph Multidigraph Pseudodigraph Inducing regularization Construction complexity |
本文献已被 ScienceDirect 等数据库收录! |
|