The oriented diameter of graphs derived from other graphs (Q7014495)

The diameter of a strong digraph or connected graph is the largest of the distances between its vertices. An orientation of an undirected graph \(G\) is a digraph obtained from \(G\) by assigning a direction to each edge. An orientation is said to be strong if the digraph is strongly connected. The oriented diameter of a graph \(G\) is the minimum diameter among all strong orientations of \(G\).\N\NIn this paper, the authors give bounds on the oriented diameter of two graphs derived from a given graph: the complement and the line graph. The authors give bounds on the oriented diameter of the complement of a graph \(G\) in terms of the diameter of \(G\) and in terms of the oriented diameter of \(G\). As a corollary, derive a Nordhaus-Gaddum-type result for the oriented diameter. The authors show that the oriented diameter of the line graph of a graph \(G\) cannot exceed the oriented diameter of \(G\) by more than 1, and that it is at least approximately the square root of the oriented diameter of \(G\). Finally, both results are proven to be the best possible in some sense.\N\NThe paper is well written and contains all the relevant previous results on the oriented diameter of graphs. It is an interesting contribution for those interested in metric graph theory.