The Degree/Diameter Problem


The Degree/Diameter Problem is to determine the largest possible number of vertices in a (di)graph where the diameter k and the maximum (out)degree d are known. A theoretical upper bound for the order is given by the Moore bound, and it has been proven that (di)graphs with this order only exists for very few values of d and k. The project aims to determine necessary properties of (di)graphs with order close to the Moore bound and thereby prove the nonexistence of such (di)graphs for most values of d and k if possible. Construction of large graphs are also an aim of the project.
Effektiv start/slut dato01/09/201001/01/2018