Springe direkt zu Inhalt

Dennis Nikolaus Natusch:

Improved upper bounds for the oriented diameter of graphs


The diameter of a graph equals the longest distance between any pair of vertices. A graph can be oriented by assigning a direction to each edge. A strongly connected orientation includes a directed path from each vertex u ∈ V (G) to each other vertex v ∈ V (G). The oriented diameter of a graph G is the minimum diameter of all strongly connected orientations of G. Let f (d) be the maximum oriented diameter of all graphs of diameter d. In other words, every 2-edge- connected graph of diameter d admits an orientation of diameter f (d) or less. Chvátal and Thomassen [2] showed the following bounds: 0.5d² + d ≤ f (d) ≤ 2d² + 2d. A recent paper by Babu, Benson, Rajendraprasad and Vaka improves the upper bound for all d ≥ 8 and d = 4 [1]. By using a similar approach, I improve the upper bounds for all d ≥ 5. None of these upper bounds could be shown to be tight, so there is room for further improvement. Additionally this thesis gives an overview of the current best results and techniques used to prove the current best results.

Bachelor of Science (B.Sc.)