Symmetry Breaking in Tournaments

Abstract

We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices $S \subseteq V(T)$ is a determining set for a tournament $T$ if every nontrivial automorphism of $T$ moves at least one vertex of $S$, while $S$ is a resolving set for $T$ if every two distinct vertices in $T$ have different distances to some vertex in $S$. We show that the minimum size of a determining set for an order $n$ tournament (its determining number) is bounded by $\lfloor n/3 \rfloor$, while the minimum size of a resolving set for an order $n$ strong tournament (its metric dimension) is bounded by $\lfloor n/2 \rfloor$. Both bounds are optimal.