Show simple item record

dc.contributor.authorZhang, Cheng
dc.date.accessioned2019-04-22T16:28:33Z
dc.date.available2019-04-22T16:28:33Z
dc.date.issued2018
dc.identifier.otherW Thesis 1559
dc.identifier.urihttp://hdl.handle.net/11040/24570
dc.descriptioniv, 58 leaves: illustrations.
dc.descriptionIncludes bibliographical references: leaves 57.
dc.description.abstractThis 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.en_US
dc.description.tableofcontents1 Introduction – 1.1 Summary of previous works – 1.2 Structure of this thesis – 2 Background – 2.1 Directed graph – 2.2 Beating relations – 2.3 Oriented graph and tournament – 2.4 Kings – 3 Semi-complete Digraph – 3.1 Definitions – 3.2 Properties – 4 Oriented graph – 5 Quasi-transitive oriented graph – 5.1 Definitions – 5.2 Tie and tie paths – 5.3 Tie components – 5.4 Graph condensations – 5.5 Tie component condensations – 5.6 Kings – 6 Further problems
dc.language.isoen_USen_US
dc.publisherWheaton College (MA).en_US
dc.subjectUndergraduate research.en_US
dc.subjectUndergraduate thesis.en_US
dc.subject.lcshDirected graphs.
dc.subject.lcshMathematics.
dc.subject.lcshGraph theory.
dc.titleKings in generalized tournaments.en_US
dc.typeThesisen_US


Files in this item

Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record