# A small graph-theory puzzle

I like to think about graph theory problems these days. Here is one:

What type of graph has minimal diameter for a given number of vertices, given an upper bound on the in-degree and another upper bound on the out-degree?

I will give eternal fame (among the readership of this blog) to anyone who can provide a practical algorithm to construct such graphs. Pointing me to a reference counts.

(No, I have not even tried to solve the problem. I am just interested in the answer.)

## 6 thoughts on “A small graph-theory puzzle”

1. So the graph is directed ? In that case, is the “distance” between a pair defined to be the shorter of uv and vu ? or is the diameter merely the max over u,v of d(uv) ?

2. D. Eppstein says:

In the undirected case, see Moore graphs for a lower bound on diameter that is achievable for some cases. The fact that we don’t know whether one of the possible cases of a Moore graph exists (the case with diameter 2, degree 57, and 3250 nodes) leads me to believe that there is no known efficient algorithm for constructing diameter-minimal graphs more generally.

3. Suresh: I’d say “max over u,v of d(uv)”. But if it is easier to solve with an alternate definition of the diameter, I’d live with it.

4. Anonymous says:

Do I understand this correctly or am I being missing something ?

Seems to me to be that for a diameter of i
the max. number of nodes is
(m+n)(m+n-1)^i

So for a given number of vertices v
the number of nodes remaining at any stage is

v – (m+n)(m+n-1)^i

for a diameter of i
find the biggest i add 1 depending on the result pending.

5. If you want the exactly minimum diameter, then that sounds like a hard combinatorial problem.

But you can get within a constant factor (in degree and diameter) with expander graphs, specifically Ramanujan graphs. A lower bound on the diameter is log(n)/log(d), and Ramanujan graphs have diameter less than 2 log(n)/log(d/4) = O(log(n)/log(d)).

The defining feature of Ramanujan graphs is that they have spectral expansion lambda

6. [Your comment form eats < signs. Is it taking raw HTML? It’d be nice to know, to avoid formatting mishaps.]

If you want the exactly minimum diameter, then that sounds like a hard combinatorial problem.

But you can get within a constant factor (in degree and diameter) with expander graphs, specifically Ramanujan graphs. A lower bound on the diameter is log(n)/log(d), and Ramanujan graphs have diameter less than 2 log(n)/log(d/4) = O(log(n)/log(d)).

The defining feature of Ramanujan graphs is that they have spectral expansion lambda < 2 srqt(d-1)/d. By considering a random walk starting from one vertex it’s not hard to show this implies a diameter at most log(n)/log(1/lambda) < 2 log(n)/log(d/4).

The Wikipedia article has references.

This is all in the undirected case, so it applies also when the in- and out-degrees are equal. Since the total in-degree equals the total out-degree, I expect it doesn’t help to allow higher in- than out-degrees or vice versa, but I don’t know.

There’s a large body of work on expanders in general, and it’s possible someone has addressed diameter specifically and closed the constant-factor gap left by the spectral approach through Ramanujan graphs.