...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Cayley graphs of diameter two and any degree with order half of the Moore bound
【24h】

Cayley graphs of diameter two and any degree with order half of the Moore bound

机译：直径为2且度数为Moore界的一半的Cayley图

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

摘要

It is well known that the number of vertices of a graph of diameter two and maximum degree d is at most d~2 + 1. The number d~2 + 1 is the Moore bound for diameter two. Let C(d, 2) denote the largest order of a Cayley graph of degree d and diameter two. Up to now, the only known construction of Cayley graphs of diameter two valid for all degrees d is a construction giving C(d, 2) > 1/4 d2+d. However, there is a construction yielding Cayley graphs of diameter two, degree d and order d~2 ? O(d 3/2) for an infinite set of degrees d of a special type. In this article we present, for any integer d ≥ 4, a construction of Cayley graphs of diameter two, degree d and of order 1/2 d~2?t for d even and of order 1/2 (d~2+d)?t for d odd, where 0 ≤ t ≤ 8 is an integer depending on the congruence class of d modulo 8. In addition, we show that, in asymptotic sense, the most of record Cayley graphs of diameter two is obtained by our construction.
机译：众所周知，直径为2且最大度为d的图形的顶点数量最多为d〜2 +1。数量d〜2 +1是直径为2的摩尔定界。令C（d，2）表示度为d和直径为2的Cayley图的最大阶数。到目前为止，唯一已知的，在所有度数d下均有效的直径为2的Cayley图构造是给出C（d，2）> 1/4 d2 + d的构造。但是，有一种构造可以产生直径为2，度d和阶数d〜2？的Cayley图。 O（d 3/2）对于特殊类型的无穷大的d集。在本文中，我们给出了对于任何d≥4的整数，构造直径为d且阶数为d且偶数为d且偶数为1/2（d〜2 + d的阶数为d且1/2 d〜2？t阶的Cayley图。 ）？t表示d奇数，其中0≤t≤8是整数，取决于d模8的同余类。此外，我们证明，在渐近意义上，通过我们的方法可获得大部分记录的直径为2的Cayley图施工。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号