# Noon lecture

On 25.10.2006 at 10:40 in S5, there is the following noon lecture:

# On the Degree/Diameter Problem for both bipartite and non-bipartite graphs

## Abstract

Degree/Diameter Problem: Given natural numbers Delta and D, to find the largest possible number of vertices (nB_{Delta,D}) n_{Delta,D} in a (bipartite) graph of maximum degree Delta and diameter at most D. An upper bound for both nB_{Delta,D} and n_{Delta,D} is given by the following expressions.

nB_{Delta,D} <= 1 + Delta + Delta(Delta-1) +...+ Delta(Delta-1)^{D-2} + (Delta-1)^{D-1}

n_{Delta,D} <= 1 + Delta + Delta(Delta-1) +...+ Delta(Delta-1)^{D-2} + Delta(Delta-1)^{D-1}

These expressions are known as the Bipartite Moore bound and as the Moore bound, and are denoted by (B(Delta,D)) M(Delta,D), respectively. We survey some old and new results about these problems, with emphasis on graphs of diameter 2, degree Delta and order M(Delta,D)-2. Finally, we give some open problems in this research area.

Webmaster: kamweb.mff.cuni.cz         Modified: 25. 02. 2019