Distinguishing Tournaments with Small Label Classes

Abstract

A $d$-distinguishing vertex (arc) labeling of a digraph is a vertex (arc) labeling using $d$ labels that is not preserved by any nontrivial automorphism. Let $\rho (T)$ (${\rho }^{\prime }(T)$) be the minimum size of a label class in a 2-distinguishing vertex (arc) labeling of a tournament $T$. Gluck's Theorem implies that $\rho (T)\le \lfloor n/2\rfloor$ for any tournament $T$ of order $n$. In this paper we construct a family of tournaments $\mathcal{H}$ such that $\rho (T)\ge \lfloor n/2\rfloor$ for any order $n$ tournament in $\mathcal{H}$. Additionally, we prove that ${\rho }^{\prime }(T)\le \lfloor 7n/36\rfloor +3$ for any tournament $T$ of order $n$ and ${\rho }^{\prime }(T)\ge \lceil n/6\rceil$ when $T\in \mathcal{H}$ and has order $n$. These results answer some open questions stated by Boutin.

11 pages, 3 figures