Kings in generalized tournaments.

Abstract

This thesis explores how to find and construct kings in three generalizations of tourna- ment: semi-complete digraphs, oriented graphs and quasi-transitive oriented graphs.In Chapter 3 and Chapter 4, we present a way to interpret semi-complete digraphs and oriented graphs as tournaments with “ties” (we call the “ties” in semi-complete digraphs “double ties”, and the “ties” in oriented graphs “ties”). In Chapter 3, we prove there exists an (n, k) semi-complete digraph if and only if n ≥ k ≥ 1, and all the (n, k) semi-complete digraphs that exist can be constructed with at most 1 double tie. In Chapter 4, we prove there exists an (n, k) oriented graph for all n ≥ k ≥ 0 except (1, 0), (2, 2), (3, 2), and (4, 4) oriented graphs, and we prove that all the (n, k) oriented graphs that exist can be constructed with at most 1 tie.The main focus of this thesis is quasi-transitive oriented graph, which is discussed in Chapter 5. We show an interesting fact that all the quasi-transitive oriented graphs can be condensed into tournaments by “tie component condensations”. Then, we show that the tie component condensation on a quasi-transitive oriented graph is a most efficient condensation to tournament in all the condensations to tournaments defined on all the oriented graph with the same tie structure. Finally we prove that the kings in a quasi- transitive oriented graph Q are related to the kings in the “underlying tournament of Q” (result of Q after tie component condensation). This result gives us a way to understand the properties of kings in quasi-transitive oriented graphs using the properties of king in tournaments.