查看“︁度-直徑問題”︁的源代码

'''度-直徑問題'''是[[圖論]]中一個問題，目的在定下最大[[直徑]]''k''及最大[[圖#基本術語|度數]]''d''後，找出擁有最多[[節點]]的[[圖]]。

假設圖以<math>G=(V,E)</math>表示，某節點的度數以<math>\deg(v)</math>表示，節點之間的最短距離以<math>d(u,v)</math>表示，則度-直徑問題是規定了
:<math>d \ge \max_{v\in V} \deg(v)</math>
:<math>k \ge \max_{u,v\in V} d(u,v)</math>
求出圖G。G的大小（以節點數衡量）受制於[[摩爾圖|摩爾上限]]，亦即節點的數目不可能多於
:<math>1+d\sum_{i=0}^{k-1}(d-1)^i</math>
已知在''k'' > 1和''d'' > 2的情況下，只有[[佩特森圖]]和{{le|Hoffman-Singleton圖|Hoffman–Singleton graph}}，以及一個''k''=2、''d''=57的圖能達到摩爾上限，一般情況下，圖的節點數目遠少於摩爾上限所指定。

== 參考文獻 ==
* {{citation
  | last1 = Bannai
  | first1 = E.
  | last2 = Ito
  | first2 = T.
  | title = On Moore graphs
  | journal = J. Fac. Sci. Univ. Tokyo Ser. A
  | volume = 20
  | pages = 191–208
  | year = 1973
  | id = {{MathSciNet | id = 0323615}}}}

* {{citation
  | last1 = Hoffman
  | first1 = Alan J.
  | last2 = Singleton
  | first2 = Robert R.
  | title = Moore graphs with diameter 2 and 3
  | journal = IBM Journal of Research and Development
  | volume = 5
  | issue = 4
  | year = 1960
  | pages = 497–504
  | url = http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf
  | id = {{MathSciNet | id = 0140437}}
  | accessdate = 2010-05-04
  | archive-date = 2008-05-18
  | archive-url = https://web.archive.org/web/20080518053636/http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf
  }}

* {{citation
  | title = There is no irregular Moore graph
  | last = Singleton
  | first = Robert R.
  | journal = [[American Mathematical Monthly]]
  | volume = 75
  | issue = 1
  | pages = 42–43
  | year = 1968
  | url = http://www.jstor.org/view/00029890/di991528/99p1853x/0
  | id = {{MathSciNet | id = 0225679}}}}

* {{citation
 |last1        = Miller
 |first1       = Mirka
 |last2        = Širáň
 |first2       = Jozef
 |title        = Moore graphs and beyond: A survey of the degree/diameter problem
 |journal      = Electronic Journal of Combinatorics
 |volume       = Dynamic survey
 |pages        = DS14
 |year         = 2005
 |url          = http://www.combinatorics.org/Surveys/ds14.pdf
 |access-date  = 2010-05-04
 |archive-url  = https://web.archive.org/web/20120118062934/http://www.combinatorics.org/Surveys/ds14.pdf
 |archive-date = 2012-01-18
 |dead-url     = yes
}}

==外部連結==
* https://web.archive.org/web/20120217054532/http://maite71.upc.es/grup_de_grafs/table_g.html/

[[Category:圖論]]
[[Category:数学问题]]