# The Degree/Diameter Problem

### From Combinatorics Wiki

## Contents |

## Introduction

### Undirected graphs

A graph *G* is a collection of points, also called vertices or nodes, and lines connecting these points, also called edges. The set of all the vertices of *G* is denoted by *V*, and the set of all edges of *G* is denoted by *E*, and therefore we can write *G* as the pair *(V,E)*. We consider only the case when *V* is finite. The set *E* can also be regarded as a subset of the 2-element subsets of *V*, where if *u* and *v* are two vertices of *G*, then the edge *e* connecting *u* to *v* is an element of the set *E*, and therefore we can write *e* as *(u,v)*, and say that *u* and *v* are adjacent. We can also say that *u* and *v* are the endvertices of the edge *e=(u,v)*.

An edge *e=(u,v)* with *u=v* is called a loop. Two edges with the same endvertices are called multiple. A simple graph is a graph without loops or multiple edges. Here we only consider simple graphs.

The number of vertices *n* in the graph *G* is the order of the graph, and is denoted by *n=|G|=|V|*.

The degree of a vertex, denoted *d(v)*, is the number of vertices adjacent to *v*. A graph *G* is *d*-regular if the degree of all the vertices in *G* is equal to *d*.

A path *P* is a sequence of distinct vertices, such that any consecutive vertices are adjacent, and non-consecutive vertices are not. A cycle is a path of at least three vertices starting and ending in the same vertex. In a graph *G* the distance between two vertices *u* and *v* is the number of edges in a shortest path starting at *u* and terminating at *v*. We denote this distance by *dist(u,v)*. If no such path exists, and hence, the graph is disconnected, we say that the distance is . The diameter *k* of *G* is the maximum pairwise distance between the vertices of the graph.

The **degree diameter problem** is the problem of finding the largest possible number *N(d,k)* of vertices in a graph of maximum degree *d* and diameter *k*.

We call a graph of maximum degree *d* and diameter *k* a *(d,k)*-graph.

An upper bound on the order of a *(d,k)*-graph is given by the expression *(d(d-1) ^{k}-2)(d-2)^{-1}*, known as the Moore bound, and denoted by

*M(d,k)*.

Graphs whose order attains the Moore bound are called Moore graphs. Moore graphs proved to be very rare. They are the complete graphs on *d+1* vertices, the cycles on *2k+1* vertices, and for diameter 2, the Petersen graph, the Hoffman-Singleton graph and probably a graph of degree *d* = 57. For 2 < *k* and 2 < *d*, there are no Moore graphs.

Consequently, research activities in the degree/diameter problem cover (i) *Constructions of ever larger graphs, which provide better lower bounds on *N(d,k)* * and (ii) *Proofs of the non-existence or otherwise of graphs whose order misses the Moore bound by a small number of vertices*. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general graphs can be found here.

### Directed graphs

If we give an orientation to each edge of *G*, then, we call *G* a directed graph, or simply digraph, and accordingly, the edges of *G* directed edges, or simply arcs. The number of arcs starting at a vertex *u* represents the out-degree of *u*, while the number of arcs arriving at a vertex *u* gives the in-degree of *u*. Two arcs *(u,v)* and *(w,t)* are adjacent if, and only if, v=w or *u=t*. A directed path is a sequence of adjacent arcs, with all the vertices distinct. The notions of a cycle, distance and diameter are defined as in the case of undirected graphs but considering the orientation of the arcs.

In the context of digraphs the degree/diameter problem can be considered as the problem of finding the largest possible number *DN(d,k)* of vertices in a digraph of maximum out-degree *d* and diameter *k*.

We call a digraph of maximum out-degree *d* and diameter *k* a *(d,k)*-digraph.

An upper bound on the order of a *(d,k)*-digraph is given by
the expression *(d ^{k+1}-1)(d-2)^{-1}*, known as the directed Moore bound, and denoted by

*DM(d,k)*.

Digraphs attaining the directed Moore bound are called Moore digraphs, and they are even rarer than the Moore graphs. Moore digraphs are the directed cycles on *k+1* vertices and the complete digraphs on *d+1* vertices. For 1 < *k* and 1 < *d*, there are no Moore digraphs. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general digraphs can be found here.

## The degree/diameter problem for several classes of graphs (ongoing project):

The following database of tables and pages is maintained and moderated by **Eyal Loz**, **Hebert Pérez-Rosés**, and **Guillermo Pineda-Villavicencio**, as part of the project **The degree/diameter problem for several classes of graphs**.

If, in addition to the limits on the degree and the diameter, we add further constraints to the graphs in question, we can state the degree/diameter problem for several classes of graphs, such as bipartite graphs, vertex-transitive graphs, Cayley graphs, arc-transitive graphs, and the corresponding versions for digraphs. In these cases we denote the largest possible number of nodes by *N ^{b}(d,k)* (for bipartite graphs),

*N*(for vertex-transitive graphs),

^{vt}(d,k)*N*(for Cayley graphs), and

^{c}(d,k)*N*(for arc-transitive graphs), respectively.

^{at}(d,k)For only a few classes of graphs, better general upper bounds are known. For information on the best upper bounds known at present for a certain class, follow the corresponding link below.

**The undirected case:**

**The directed case:**

## References

- Bannai, E.; Ito, T. (1973), "On finite Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208, MR0323615
- Bridges, W. G.; Toueg, S. (1980), "On the impossibility of directed Moore graphs", Journal of Combinatorial Theory, Series B 29 (3), 339--341, doi:10.1016/0095-8956(80)90091-X.
- Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, MR0140437, PDF version
- Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly 75 (1): 42–43, MR0225679
- Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey DS14 PDF version.