Back to search

Clemson University

A set of tournaments with many Hamiltonian cycles

Abstract

dc:description.abstract

For a random tournament on 3n vertices, the expected number of Hamiltonian cycles is known to be (3n -1)!/23n. Let T1 denote a tournament of three vertices {v1, v2, v3}. Let the orientation be such that there are directed edges from v1 to v2 , from v2 to v3 and from v3 to v1. Construct a tournament Ti by making three copies of Ti-1, Ti-1', Ti-1'' and Ti-1'''. Let each vertex in Ti-1' have directed edges to all vertices in Ti-1'', similarly place directed edges from each vertex in Ti-1'' to all vertices in Ti-1''' and from Ti-1''' to Ti-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.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematical Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ushijima-mwesigwa, Hayato
Contributors dc:contributor
  • Calkin, Neil
  • Novick , Beth
  • Warner , Daniel

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/1422

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ushijima-mwesigwa, Hayato. A set of tournaments with many Hamiltonian cycles. Thesis thesis, https://open.clemson.edu/all_theses/1422