度-直徑問題

维基百科,自由的百科全书
跳转至: 导航搜索

度-直徑問題圖論中一個問題,目的在定下最大直徑k及最大度數d後,找出擁有最多節點

假設圖以G=(V,E)表示,某節點的度數以\deg(v)表示,節點之間的最短距離以d(u,v)表示,則度-直徑問題是規定了

d \ge \max_{v\in V} \deg(v)
k \ge \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 

外部鏈接[编辑]