度-直徑問題

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

外部連結