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.)
Follow me on twitter!
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) ?
Comment by Suresh — 10/7/2008 @ 13:48
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.
Comment by D. Eppstein — 10/7/2008 @ 13:59
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.
Comment by Daniel Lemire — 10/7/2008 @ 16:52
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.
Comment by Anonymous — 12/7/2008 @ 18:28
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
Comment by Greg Price — 19/7/2008 @ 17:12
[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.
Comment by Greg Price — 19/7/2008 @ 17:15