首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 View the MathML source being the maximum among semi-degrees in D, simple n-vertex digraphs D with largest possible ρ are characterized if either View the MathML source or View the MathML source (where the case View the MathML source is not a trivial subcase of View the MathML source).
Keywords:Regular digraph  Multidigraph  Pseudodigraph  Inducing regularization  Construction complexity
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号