度-直径问题

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

假设图以$G=(V,E)$表示，某节点的度数以$\deg(v)$表示，节点之间的最短距离以$d(u,v)$表示，则度-直径问题是规定了

$d\geq \max _{v\in V}\deg(v)$

$k\geq \max _{u,v\in V}d(u,v)$

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

$1+d\sum _{i=0}^{k-1}(d-1)^{i}$

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

参考文献

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

• Hoffman, Alan J.; Singleton, Robert R., Moore graphs with diameter 2 and 3 (PDF), IBM Journal of Research and Development, 1960, 5 (4): 497–504 [2010-05-04], MR0140437, （原始内容 (PDF)存档于2008-05-18） 

• Singleton, Robert R., There is no irregular Moore graph, American Mathematical Monthly, 1968, 75 (1): 42–43, MR0225679 

• Miller, Mirka; Širáň, Jozef, Moore graphs and beyond: A survey of the degree/diameter problem (PDF), Electronic Journal of Combinatorics, 2005,, Dynamic survey: DS14 [2010-05-04], （原始内容 (PDF)存档于2012-01-18） 

外部链接

• https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/