度-直徑問題

度-直徑問題是圖論中一個問題，目的在定下最大直徑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/