Extremal Results on Arc-Traceable Tournaments

Abstract

A tournament $T=(V,A)$ is $arc-traceable$ if for each arc $xy\in A$, $xy$ lies on a directed path containing all the vertices of $V$, i.e., a hamiltonian path. In this paper, we give two extremal results related to arc-traceability in tournaments. First, we show that a non-arc-traceable tournament $T$ which is $m$-arc-strong must have at least $2^{m+1}+4m-3$ vertices, and we construct an example that shows that this result is best possible. Next, we consider the maximum number of arcs in a strong tournament that are not part of any hamiltonian path. We use the structure of non-arc-traceable tournaments to prove that no strong tournament contains more than $\frac{n^2-4n+3}{8}$ arcs that are not part of a hamiltonian path, and we give the unique example that shows that this bound is best possible.