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) ?
D. Eppsteinsays:
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.
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
[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).
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.
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) ?
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.
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.
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.
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
[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.