随机扰动有向图的泛圈性  

Pancyclicity of randomly perturbed digraph

作　　者：任泽林 侯新民 Zelin Ren;Xinmin Hou(School of Cyber Science and Technology,University of Science and Technology of China,Hefei 230022,China;Wu Wen-Tsun Key Laboratory of Mathematics,School of Mathematical Sciences,University of Science and Technology of China,Hefei 230026,China)

机构地区：[1]中国科学技术大学网络空间学院,安徽合肥230022 [2]中国科学技术大学数学科学学院吴文俊数学重点实验室,安徽合肥230026

出　　处：《中国科学技术大学学报》2022年第5期11-16,I0002,共7页JUSTC

基　　金：supported by National Natural Science Foundation of China (12071453);the National Key R&D Program of China (2020YFA0713100)。

摘　　要：Dirac定理指如果n个顶点的图G最小度至少为n/2,则G包含一个哈密尔顿圈. Bohman等引入了随机扰动图模型并证明了对任意正常数α和最小度至少为αn的图H,存在一个仅依赖于α的常数C使得对任意p≥C/n H∪G_(n,p)是几乎渐进肯定哈密尔顿的。本文考虑了随机扰动有向图模型,证明了对任意α=ω{(logn/n)^(1/4)}和d∈{1, 2},一个最小度至少αn的n点有向图和随机d正则有向图是几乎渐进肯定泛圈的。更进一步,给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least n/2,then G contains a Hamiltonian cycle.Bohman et al.introduced the random perturbed graph model and proved that for any constant α>0 and a graph H with a minimum degree of at least αn,there exists a constant C depending on α such that for any p≥C/n H∪G_(n,p),is asymptotically almost surely(a.a.s.) Hamiltonian.In this study,the random perturbed digraph model is considered,and we show that for all α=ω{(logn/n)^(1/4)} and d∈{1,2},the union of a digraph on n vertices with a minimum degree of at least and a random d-regular digraph on n vertices is a.a.s.pancyclic.Moreover,a polynomial-time algorithm is proposed to find cycles of any length in such a digraph.

关 键 词：随机扰动图 泛圈 吸收方法 算法 

分 类 号：O157.5[理学—数学]