Date of Award

8-2012

Document Type

Thesis

Degree Name

Master of Science (MS)

Legacy Department

Mathematical Science

Committee Chair/Advisor

Calkin, Neil

Committee Member

Novick , Beth

Committee Member

Warner , Daniel

Abstract

For a random tournament on $3^n$ vertices, the expected number of Hamiltonian cycles is known to be $(3^n -1)!/2^{3^n}$. Let $T_1$ denote a tournament of three vertices $ {v_1, v_2, v_3}$. Let the orientation be such that there are directed edges from $v_1 $to $v_2$ , from $v_2$ to $v_3$ and from $v_3$ to $ v_1$. Construct a tournament $T_i$ by making three copies of $T_{i-1}$, $T_{i-1}'$, $T_{i-1}''$ and $T_{i-1}'''$. Let each vertex in $T_{i-1}'$ have directed edges to all vertices in $T_{i-1}''$, similarly place directed edges from each vertex in $T_{i-1}''$ to all vertices in $T_{i-1}'''$ and from $T_{i-1}'''$ to $T_{i-1}'$.
In this thesis, we shall study this family of highly symmetric tournaments. In particular we shall present two different algorithms to calculate the number of Hamiltonian cycles in these tournaments and compare them with the expected number and with known bounds for random tournaments. This thesis is motivated by the question of the maximum number of Hamiltonian cycles a tournament can have.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.