...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On bipartite graphs of defect at most 4
【24h】

On bipartite graphs of defect at most 4

机译：在缺陷最多为4的二部图中

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

摘要

We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Δ<2 and D<2, find the maximum number N b(Δ,D) of vertices in a bipartite graph of maximum degree Δ and diameter D. In this context, the Moore bipartite bound M_b(Δ,D) represents an upper bound for Nb(Δ,D). Bipartite graphs of maximum degree Δ, diameter D and order M_b(Δ,D)called Moore bipartite graphshave turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Δ<2, diameter D<2 and order Mb(Δ,D)- with small >0, that is, bipartite (Δ,D,-)-graphs. The parameter is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if Δ<3 and D<3, they may only exist for D=3. However, when >2 bipartite (Δ,D,-)-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite (Δ,D,-4)-graphs; the complete catalogue of bipartite (3,D,-)-graphs with D<2 and 0≤≤4; the complete catalogue of bipartite (Δ,D,-)-graphs with Δ<2, 5≤D≤187 (D≠6) and 0≤≤4; a proof of the non-existence of all bipartite (Δ,D,-4)-graphs with Δ<3 and odd D<5. Finally, we conjecture that there are no bipartite graphs of defect 4 for Δ<3 and D<5, and comment on some implications of our results for the upper bounds of Nb(Δ,D).
机译：我们考虑度数/直径问题的二部形式，即给定自然数Δ<2和D <2，在最大度Δ和直径D的二部图中找到顶点的最大数目N b（Δ，D）。在此上下文中，摩尔二分界M_b（Δ，D）表示Nb（Δ，D）的上限。结果发现，最大度数Δ，直径D和阶数M_b（Δ，D）的二分图被称为摩尔二分图，这是非常罕见的。因此，研究最大度Δ<2，直径D <2和阶数Mb（Δ，D）-且> 0小的二部图（即二部图（Δ，D，-））非常有趣。该参数称为缺陷。本文最多考虑4个缺陷的二部图，并提出所有已知的此类图。过去已经研究了缺陷2的二部图。如果Δ<3和D <3，则它们仅在D = 3时才存在。但是，当> 2的二部图（Δ，D，-）图表示未开发的区域较大时。本文的主要结果包括存在二分图（Δ，D，-4）图的几个必要条件; D <2和0≤≤4的二部（3，D，-）图的完整目录; Δ<2、5≤D≤187（D≠6）和0≤≤4的二部（Δ，D，-）图的完整目录;证明所有不存在Δ<3和奇数D <5的二分（Δ，D，-4）图的证据。最后，我们猜想对于Δ<3和D <5，没有缺陷4的二部图，并评论了我们的结果对Nb（Δ，D）上限的一些暗示。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号