, 1 min read
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.)