minimal average distances between $n$ nodes in a directed graph

Question

I have a directed graph with $n$ nodes.

for any paired of nodes $A,B$, there is a directed edge that goes in between, but it can't go both ways. i.e. $A \rightarrow B$ and $B \rightarrow A$ cannot exist at the same time.

Let the distance between $A$ to $B$ be the number of edges we travel. How do we arrange the edges, so that the average distance, between all ordered pairs of $A,B$ in the graph, is minimized?

This frankly seems like an simple setup that should come with some known answer, but googling couldn't give me anything useful.

I found http://mathworld.wolfram.com/WienerIndex.html though, but not sure where my example would fall..

Answer 1

For each pair of distinct vertices $(x,y)$, we have $$d(x,y) + d(y,x) \ge 3$$ because each distance is at most $1$, and both of the distances cannot be $1$ simultaneously: that would require an arc $x \to y$ and an arc $y \to x$ to exist at the same time. So the average $\frac{d(x,y) + d(y,x)}{2}$ is at least $\frac32$, and therefore the average over the whole graph is at least $\frac32$.

We achieve this average if we have a tournament in which $d(x,y) \le 2$ for all $x,y$: if the tournament has diameter $2$. In that case, for every pair of distinct vertices $(x,y)$, we either have an arc $x \to y$ (in which case $d(x,y) = 1$ and $d(y,x)=2$) or an arc $y \to x$ (in which case $d(x,y)=2$ and $d(y,x)=1$). Therefore the average $\frac{d(x,y) + d(y,x)}{2}$ is exactly $\frac32$, and this makes the average over the whole graph exactly $\frac32$.

For odd $n$, there is an easy construction: arrange the $n$ points in a circle, and from each point, draw an arc to the next $\frac{n-1}{2}$ points counter-clockwise from it. Here is an example (source):

For even $n \ge 6$, draw the $n-1$ configuration, then put a point in the center which mostly alternates "arc going in" and "arc going out" around the circle. We're going to have one place where the alternating pattern breaks, because $n-1$ is odd, but that's going to be fine for $n\ge 6$.

For $n=4$, unfortunately, diameter $2$ is impossible: there will be one distance of $3$, so the average of the distances will be $\frac32 + \frac1{12} = \frac{19}{12}$.

Answer 2

The type of graph you are looking for it called a tournament. You might be interested in corollary 3 here or in this article. I'm not completely sure if you are interested in exactly the same notion of average distance (there are many ways to define it, but they are all somewhat related) but in the first article, it is shown that if we use the definition$$\mu(G)=\frac{1}{n(n-1)}\sum_{x,y\in V(G)}d(x,y)$$ then for tournaments $T$, $$\mu(T)\geq \frac{3}{2}$$which is achieved for $n\neq 4$ by tournaments of diameter 2, but I strongly suggest you take a look at the articles.