度-直徑問題 度直徑問題是圖論中一個問題目的在定下最大直徑k及最大度數d後找出擁有最多節點的圖 假設圖以 G   V  E  displaystyle GVE 表示某節點的度數以 deg   v  displaystyle degv 表示節點之間的最短距離以 d  u  v  displaystyle duv 表示則度直徑問題是規定了 d  max v  V deg   v  displaystyle dgeq max vin Vdegv k  max u  v  V d  u  v  displaystyle kgeq max uvin Vduv 求出圖GG的大小以節點數衡量受制於摩爾上限亦即節點的數目不可能多於   d  i   k    d    i displaystyle dsum ikdi 已知在k  和d  的情況下只有佩特森圖和HoffmanSingleton圖英语HoffmanSingleton graph以及一個kd的圖能達到摩爾上限一般情況下圖的節點數目遠少於摩爾上限所指定