...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >RESILIENT PANCYCLICITY OF RANDOM AND PSEUDORANDOM GRAPHS
【24h】

RESILIENT PANCYCLICITY OF RANDOM AND PSEUDORANDOM GRAPHS

机译：随机和伪随机图的弹性泛滥

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A graph G on n vertices is pancyclic if it contains cycles of length t for all 3 ≤ t≤ n. In this paper we prove that for any fixed ε > 0, the random graph G(n,p) with p(n)》 n~1/2 (i.e., with p(n)~1/2 tending to infinity) asymptotically almost surely has the following resilience property. If H is a subgraph of G with maximum degree at most (1/2 —ε)np, then G — H is pancyclic. In fact, we prove a more general result which says that if p》 n~1+1/(1-1) for some integer l ≥ 3, then for any ε > 0, asymptotically almost surely every subgraph of G(n,p) with minimum degree greater than (1/2 + ε)np contains cycles of length t for all l ≤ t≤ n. These results are tight in two ways. First, the condition on p essentially cannot be relaxed. Second, it is impossible to improve the constant 1/2 in the assumption for the minimum degree. We also prove corresponding results for pseudorandom graphs.
机译：如果对所有3≤t≤n都包含长度为t的循环，则n个顶点上的图G为全循环。本文证明，对于任何固定的ε> 0，随机图G（n，p）具有p（n）》 n〜1/2（即p（n）/ n〜1/2趋于无穷大） ）几乎肯定具有以下弹性。如果H是G的子图，最大程度为（1/2-ε）np，则G-H为全环。实际上，我们证明了一个更笼统的结果，即如果对于某些整数l≥3，p〉 n〜1 + 1 /（1-1），那么对于任何ε> 0，几乎可以肯定地渐近确定G（n，最小度数大于（1/2 +ε）np的p）对于所有l≤t≤n都包含长度为t的循环。这些结果在两个方面都很严格。首先，p上的条件基本上不能放松。第二，在最小度的假设中不可能提高常数1/2。我们还证明了伪随机图的相应结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号