The Degree/Diameter Problem

From Combinatorics Wiki

Jump to: navigation, search

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 \infin. 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-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, Guillermo Pineda-Villavicencio and Ramiro Feria-Puron, 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:

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.