The oriented diameter of graphs derived from other graphs
Peter Dankelmann, Yubao Guo, Emily Rivett-Carnac, Lutz Volkmann · Discrete Mathematics · 2025
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 amongst all strong orientations of G . In this paper we give bounds on the oriented diameter of two graphs derived from a given graph: the complement and the line graph. We 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, we obtain Nordhaus-Gaddum type results for the oriented diameter. We prove 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 . We show that both results, in some sense, are best possible.