Symmetry Breaking in Tournaments

We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S⊆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 ⌊n/3⌋, while the minimum size of a resolving set for an order n strong tournament (its metric dimension) is bounded by ⌊n/2⌋. Both bounds are optimal.