Symmetry breaking in tournaments (Q1953461)

Summary: 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.