Various Theorems on Tournaments

arXiv1207.0237MaRDI QIDQ6234081FDOQ6234081

Authors: Gaku Liu 

Publication date: 1 July 2012

Abstract: In this thesis we prove a variety of theorems on tournaments. A emph{prime} tournament is a tournament $G$ such that there is no $XsubseteqV(G)$, $1<|X|<|V(G)|$, such that for every vertex $vinV(G)minusX$, either $vax$ for all $xinX$ or $xav$ for all $xinX$. First, we prove that given a prime tournament $G$ which is not in one of three special families of tournaments, for any prime subtournament $H$ of $G$ with $5le|V(H)|<|V(G)|$ there exists a prime subtournament of $G$ with $|V(H)|+1$ vertices that has a subtournament isomorphic to $H$. We next prove that for any two cyclic triangles $C$, $C^{p}rime$ in a prime tournament $G$, there is a sequence of cyclic triangles $C_1,\mathrm{...},C_n$ such that $C_1=C$, $C_n=C^{p}rime$, and $C_i$ shares an edge with $C_{i+1}$ for all $1leilen-1$. Next, we consider what we call emph{matching tournaments}, tournaments whose vertices can be ordered in a horizontal line so that every vertex is the head or tail of at most one edge that points right-to-left. We determine the conditions under which a tournament can have two different orderings satisfying the above conditions. We also prove that there are infinitely many minimal tournaments that are not matching tournaments. Finally, we consider the tournaments $K_n$ and $K_n^{a}st$, which are obtained from the transitive tournament with $n$ vertices by reversing the edge from the second vertex to the last vertex and from the first vertex to the second-to-last vertex, respectively. We prove a structure theorem describing tournaments which exclude $K_n$ and $K_n^{a}st$ as subtournaments.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

This page was built for publication: Various Theorems on Tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6234081)