1
$\begingroup$

Are there positive integers $\Delta, d$ such that the following statement is true?

For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$, $\Delta(G) \leq \Delta$ (where $\Delta(G)$ is the maximum degree of $G$), and $\text{diam}(G) \leq d$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

A graph of maximum degree $\leq \Delta$, and diameter $\leq d$ can have at most $1+\Delta\sum_{i=0}^{d-1} (\Delta-1)^i$ vertices. The graphs which attain this bound are called Moore graphs.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .