跳转到内容

度-直径问题

维基百科,自由的百科全书

度-直径问题图论中一个问题,目的在定下最大直径k及最大度数d后,找出拥有最多节点

假设图以表示,某节点的度数以表示,节点之间的最短距离以表示,则度-直径问题是规定了

求出图G。G的大小(以节点数衡量)受制于摩尔上限,亦即节点的数目不可能多于

已知在k > 1和d > 2的情况下,只有佩特森图Hoffman-Singleton图英语Hoffman–Singleton graph,以及一个k=2、d=57的图能达到摩尔上限,一般情况下,图的节点数目远少于摩尔上限所指定。

参考文献

  • Bannai, E.; Ito, T., On Moore graphs, J. Fac. Sci. Univ. Tokyo Ser. A, 1973, 20: 191–208, MR0323615 

外部链接