The oriented diameter of graphs derived from other graphs

Discrete Mathematics, vol. 348, pp. 114443

Abstract

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.

Authors 4

1. Peter Dankelmann corresponding

   University of Johannesburg

   Affiliation as printed

   Department of Mathematics and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa

2. Yubao Guo Aachen Chair for Mathematics of Information Processing

   RWTH Aachen University

   Affiliation as printed

   Chair for Mathematics of Information Processing, RWTH Aachen University, Aachen, Germany

3. Emily Rivett-Carnac

   University of Johannesburg

   Affiliation as printed

   Department of Mathematics and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa

4. Lutz Volkmann Aachen Chair for Mathematics of Information Processing

   RWTH Aachen University

   Affiliation as printed

   Chair for Mathematics of Information Processing, RWTH Aachen University, Aachen, Germany