Date of Graduation
1995
Document Type
Dissertation/Thesis
Abstract
A digraph D is called semicomplete if for each pair of distinct vertices u, v {dollar}\\in{dollar} V(D), either uv, vu or both are arcs in D. This structure is a generalization of the tournament which allows only uv or vu but not both to be in the arc set. In this paper we consider theorems concerning paths and cycles in tournaments and examine whether these theorems are also true for semicomplete digraphs. The focus is on theorems pertaining to the arc-pancyclic property of semicomplete digraphs. Three very useful lemmas are presented: Thomassen's Hamiltonian Path Lemma, The Crossing Arcs Lemma for Reduction, and The Crossing Arcs Lemma for Expansion. The last two lemmas were originally proved for tournaments, and here are generalized and proved for semicomplete digraphs. Two of the main results of this paper deal with the arc-pancyclic property of almost regular semicomplete digraphs and generalize an early result of Alspach. Other results have to do with the arc-pancyclic property in arc-3-cyclic semicomplete digraphs and generalizes a theorem of Wu, Zhang and Zhou. A summary of other types of theorems pertaining to paths and cycles in semicomplete digraphs and tournaments is included in the final chapter.
Recommended Citation
Darrah, Marjorie Anne, "Paths and cycles in semicomplete digraphs." (1995). Graduate Theses, Dissertations, and Problem Reports. 8715.
https://researchrepository.wvu.edu/etd/8715