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 Kn with some edges removed. We will show that given Kn with n >= 5 and any collection of edges Ev, with |Ev| = 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.

Rights

© 2018, Garner Paul Cochran

Download

Included in

Mathematics Commons

Share

COinS