## Date of Award

2018

## Document Type

Open Access Dissertation

## Department

Mathematics

## Sub-Department

College of Arts and Sciences

## First Advisor

Eva Czabarka

## Abstract

In this dissertation, I will discuss two results on the oriented diameter of graphs with certain properties. In the first problem, I studied the oriented diameter of a graph G. Erdos et al. in 1989 showed that for any graph with |V | = n and δ(G) = δ the maximum the diameter could possibly be was 3 n/ δ+1. I considered whether there exists an orientation on a given graph with |G| = n and δ(G) = δ that has a small diameter. Bau and Dankelmann (2015) showed that there is an orientation of diameter 11 n/ δ+1 + O(1), and showed that there is a graph which the best orientation admitted is 3 n/ δ+1 + O(1). It was left as an open question whether the factor of 11 in the first result could be reduced to 3. The result above was improved to 7 n / δ+1 +O(1) by Surmacs (2017) and I will present a proof of a further improvement of this bound to 5 n/δ−1 + O(1). It remains open whether 3 is the best answer. In the second problem, I studied the oriented diameter of the complete graph K_{n} with some edges removed. We will show that given Kn with n >= 5 and any collection of edges E^{v}, with |E^{v}| = n − 5, that there is an orientation of this graph with diameter 2. It remains a question how many edges we can remove to guarantee larger diameters.

## Recommended Citation

Cochran, G. P.(2018). *Quick Trips: On the Oriented Diameter of Graphs.* (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/4671