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. 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. 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.

  4. 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

  5. [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.

Leave a Reply

Your email address will not be published. Required fields are marked *