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.svg|thumb|upright=1.1|When the degree is less than or equal to 2 or the 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 {{mvar|G}} (in terms of the size of its vertex set {{mvar|V}}) of diameter {{mvar|k}} such that the largest 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 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 conjectured 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>.

== 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 = https://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