View source for Degree diameter problem

{{Short description|Finding the largest graph of given diameter and degree}}
{{unsolved|mathematics|Given two positive integers {{mvar|d}}, {{mvar|k}}, what is the largest graph of diameter {{mvar|k}} such that all vertices have degrees at most {{mvar|d}}?}}
{{No footnotes|date=November 2024}}
[[File:Degree-Diameter trivials.png|thumb|400px|When the [[degree (graph theory)|degree]] is less than or equal to 2 or the [[Diameter (graph theory)|diameter]] is less than or equal to 1, the problem becomes trivial, solved by the [[cycle graph]] and [[complete graph]] respectively.]]
In [[graph theory]], the '''degree diameter problem''' is the problem of finding the largest possible [[graph (discrete mathematics)|graph]] {{mvar|G}} (in terms of the size of its [[vertex (graph theory)|vertex]] set {{mvar|V}}) of [[Diameter (graph theory)|diameter]] {{mvar|k}} such that the largest [[degree (graph theory)|degree]] of any of the vertices in {{mvar|G}} is at most {{mvar|d}}. The size of {{mvar|G}} is bounded above by the [[Moore graph|Moore bound]]; for {{math|1 < ''k''}} and {{math|2 < ''d''}}, only the [[Petersen graph]], the [[Hoffman-Singleton graph]], and possibly graphs (not yet proven to exist) of diameter {{math|1=''k'' = 2}} and degree {{math|1=''d'' = 57}} attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound.

== Formula ==
Let <math>n_{d,k}</math> be the maximum possible number of vertices for a graph with degree at most ''d'' and diameter ''k''. Then <math>n_{d,k}\leq M_{d,k}</math>, where <math>M_{d,k}</math> is the [[Moore bound]]:

:<math>M_{d,k} = \begin{cases}1 + d\frac{(d-1)^k-1}{d-2} & \text{ if }d>2 \\ 2k+1 & \text{ if }d=2\end{cases}</math>

This bound is attained for very few graphs, thus the study moves to how close there exist graphs to the Moore bound.
For asymptotic behaviour note that <math>M_{d,k} = d^k + O(d^{k-1})</math>.

Define the parameter <math>\mu_k=\liminf_{d\to\infty}\frac{n_{d,k}}{d^k}</math>. It is [[conjecture]]d that <math>\mu_k=1</math> for all ''k''. It is known that <math>\mu_1=\mu_2=\mu_3=\mu_5=1</math> and that <math>\mu_4\geq 1/4</math>.

==See also==
* [[Cage (graph theory)]]
* [[Table of the largest known graphs of a given diameter and maximal degree]]
* [[Table of vertex-symmetric digraphs|Table of vertex-symmetric degree diameter digraphs]]
* [[MaxDDBS|Maximum degree-and-diameter-bounded subgraph problem]]

== References ==
{{refbegin}}
* {{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
  | mr = 0323615 }}
* {{citation
  | author1-link = Alan Hoffman (mathematician)
  | 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
  | mr = 0140437
  | doi=10.1147/rd.45.0497}}
* {{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
  | jstor = 2315106
  | mr = 0225679 
  | doi = 10.2307/2315106
  | publisher = Mathematical Association of America}}
* {{citation
  | last1 = Miller
  | first1 = Mirka | author1-link = Mirka Miller
  | 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/ojs/index.php/eljc/article/download/DS14/pdf}}
* {{citation
  | title = CombinatoricsWiki - The Degree/Diameter Problem
  | url = http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem}}
{{refend}}

[[Category:Computational problems in graph theory]]
[[Category:Graph distance]]


{{hyperbolic-geometry-stub}}
{{graph-stub}}