Appears in collection : Cayley graphs and the degree-diameter problem

The degree-diameter problem is to determine the largest number of vertices in a graph of maximum degree $d$ and diameter $k$. The problem is motivated by network design. The topology of a network (such as telecommunications, multiprocessor, or local area network) is usually modelled by a graph in which vertices represent nodes (stations or processors) while edges stand for links or other types of connections. The network interpretation of the two parameters (diameter of a graph and vertex degrees) is obvious. The degree of a vertex is the number of connections attached to a node, while the diameter indicates the largest number of links that must be traversed in order to transmit a message between any two nodes. It is known that the number of vertices in a graph of maximum degree $d$ and diameter $k$ cannot exceed the Moore bound. Research activities related to the degree-diameter problem fall into two main streams. On one hand there are proofs of non-existence of graphs of order close to the Moore bound, on the other hand there is a great deal of activity in constructions of large graphs of given maximum degree and diameter. I present definitions, introduction and some results in this area in a simple way, so also students will be able to follow the lectures.