度-直徑問題

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

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

$d\ge \underset{v\in V}{\max }\mathrm{deg}(v)$

$k\ge \underset{u,v\in V}{\max }d(u,v)$

求出圖G。G的大小（以節點數衡量）受制於摩爾上限，亦即節點的數目不可能多於

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

已知在k > 1和d > 2的情況下，只有佩特森圖和Template:Le，以及一個k=2、d=57的圖能達到摩爾上限，一般情況下，圖的節點數目遠少於摩爾上限所指定。

參考文獻

• Template:Citation

• Template:Citation

• Template:Citation

• Template:Citation

外部連結

• -{R|https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/}-