• 中文核心期刊要目总览
  • 中国科技核心期刊
  • 中国科学引文数据库(CSCD)
  • 中国科技论文与引文数据库(CSTPCD)
  • 中国学术期刊文摘数据库(CSAD)
  • 中国学术期刊(网络版)(CNKI)
  • 中文科技期刊数据库
  • 万方数据知识服务平台
  • 中国超星期刊域出版平台
  • 国家科技学术期刊开放平台
  • 荷兰文摘与引文数据库(SCOPUS)
  • 日本科学技术振兴机构数据库(JST)

随机扰动有向图的泛圈性

Pancyclicity of randomly perturbed digraph

  • 摘要: Dirac定理指如果n个顶点的图G最小度至少为n/2,则G包含一个哈密尔顿圈. Bohman 等引入了随机扰动图模型并证明了对任意正常数α和最小度至少为αn的图H, 存在一个仅依赖于α的常数 C 使得对任意pC/nHGnp 是几乎渐进肯定哈密尔顿的。 本文考虑了随机扰动有向图模型,证明了对任意\alpha = \omega \left( \left( \frac\log nn \right)^\textstyle1 \over 4 \right)d \in \ 1,2\ ,一个最小度至少αnn点有向图和随机d正则有向图是几乎渐进肯定泛圈的。更进一步,给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。

     

    Abstract: Dirac’s theorem states that if a graph G on n vertices has a minimum degree of at least \displaystyle \fracn2, then G contains a Hamiltonian cycle. Bohman et al. introduced the random perturbed graph model and proved that for any constant \alpha > 0 and a graph H with a minimum degree of at least \alpha n , there exists a constant C depending on α such that for any p \geqslant \dfracCn, H \cup 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 \alpha = \omega \left( \left( \dfrac\log nn \right)^\textstyle1 \over 4 \right) and d \in \ 1,2\, the union of a digraph on n vertices with a minimum degree of at least \alpha n 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.

     

/

返回文章
返回