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}}?}}

File:Degree-Diameter trivials.png 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 $n_{d,k}$ be the maximum possible number of vertices for a graph with degree at most d and diameter k. Then $n_{d,k}\leq M_{d,k}$ , where $M_{d,k}$ is the Moore bound:

: $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}$

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 $M_{d,k} = d^k + O(d^{k-1})$ .

Define the parameter $\mu_k=\liminf_{d\to\infty}\frac{n_{d,k}}{d^k}$ . It is conjectured that $\mu_k=1$ for all k. It is known that $\mu_1=\mu_2=\mu_3=\mu_5=1$ and that $\mu_4\geq 1/4$ .

References

{{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}}

Category:Computational problems in graph theory

Category:Graph distance

Degree diameter problem

Formula

See also

References