The Degree/Diameter Problem

From Combinatorics Wiki

Citation

If you are using combinatoricsWiki, then we would like to ask you to cite the site as follows.

If you are using a specific page in combinatoricsWiki, say the "The degree-diameter problem" page, then it would be better to cite the page as follows.

  • E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). The degree-diameter problem, Combinatorics Wiki, http://combinatoricswiki.org.

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 [math]\infty[/math]. 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 (dk+1-1)(d-1)-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.

Mixed graphs

A mixed graph (also known as partially directed graph) [math]G[/math] may contain (undirected) edges as well as directed edges (also known as arcs or darts). Hence, mixed graphs generalize both undirected and directed graphs. Nevertheless, here we suppose that mixed graphs contain at least one edge and one arc. The undirected degree of a vertex [math]v[/math], denoted by [math]d(v)[/math] is the number of edges incident to [math]v[/math]. The out-degree [resp. in-degree] of [math]v[/math], denoted by [math]d^+(v)[/math] [resp. [math]d^-(v)[/math]], is the number of arcs emanating from [resp. to] [math]v[/math]. If [math]d^+(v)=d^-(v)=z[/math] and [math]d(v)=r[/math], for all vertex [math]v[/math] in [math]G[/math], then [math]G[/math] is said to be totally regular of degree [math]d[/math], where [math]d=r+z[/math]. A em trail from [math]u[/math] to [math]v[/math] of length [math]l[/math] is a sequence of [math]l+1[/math] vertices, such that the first vertex of the sequence is [math]u[/math] and the last one is [math]v[/math] and each pair of consecutive vertices of the sequence is either an edge or an arc of [math]G[/math]. The notions of path, distance and diameter are defined as in the previous cases, but allowing edges and arcs both together. Note that the distance from [math]u[/math] to [math]v[/math] may be different than the reverse distance from [math]v[/math] to [math]u[/math] when shortest paths between these vertices involve arcs.

In the context of mixed graphs the degree/diameter problem can be considered as the problem of finding the largest possible number [math]N(r,z,k)[/math] of vertices in a mixed graph of maximum undirected degree [math]r[/math], maximum directed out-degree [math]z[/math] and diameter [math]k[/math].

An upper bound for [math]N(r,z,k)[/math] is given by the expression [math]A(u^{k+1}-1)(u-1)^{-1}+B(w^{k+1}-1)(w-1)^{-1} [/math], where [math]v=(z+r)^2+2(z-r)+1[/math], [math]u=(1/2)(z+r-1-v^{1/2})[/math], [math]w=(1/2)(z+r-1+v^{1/2})[/math], [math]A=(v^{1/2}-(z+r+1))(2v^{1/2})^{-1}[/math] and [math]B=(v^{1/2}+(z+r+1))(2v^{1/2})^{-1}[/math]. This is known as the mixed Moore bound, and it is denoted by [math]M(r,z,k)[/math].

Mixed graphs of order [math]M(r,z,k)[/math] with maximum undirected degree [math]r[/math], maximum directed out-degree [math]z[/math] and diameter [math]k[/math] are called mixed Moore graphs. Such extremal mixed graphs are totally regular of degree [math]d=r+z[/math] and they have the property that for any ordered pair [math](u,v)[/math] of vertices there is a unique trail from [math]u[/math] to [math]v[/math] of length at most the (finite) diameter [math]k[/math]. These extremal mixed graphs may only exist for diameter two and some (infinitely many) values of [math]M(r,z,2)[/math], although their existence has been proved only for 'few' cases. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general mixed graphs 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, Guillermo Pineda-Villavicencio, and Nacho López 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 Nb(d,k) (for bipartite graphs), Nvt(d,k) (for vertex-transitive graphs), Nc(d,k) (for Cayley graphs), and Nat(d,k) (for arc-transitive graphs), respectively.

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:

The mixed case:

References

  • Bannai, E.; Ito, T. (1973), "On finite Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208, MR0323615
  • Bosàk, J., (1978), "Partially directed Moore graphs", Math. Slovaca, (29):181–196. PDF version
  • 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.
Retrieved from ‘http://combinatoricswiki.org/index.php?title=The_Degree/Diameter_Problem&oldid=639’