Symmetry breaking in tournaments

Antoni Lozano¹

¹Universitat Politècnica de Catalunya

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

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.

Détail

DOI : 10.37236/3182

Classification : 05C12, 05C20
Mots-clés : metric dimension, determining number, tournament graph, minimum size of determining set