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 ρ(T) (ρ′(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 ρ(T) ≤ n/2 for any tournament T of order n. We construct a family of tournaments H such that ρ(T) ≥ n/2 for any tournament of order n in H. Additionally, we prove that ρ′(T ) ≤ 7n/36 + 3 for any tournament T of order n and ρ′(T ) ≥ n/6 when T ∈ H and has order n. These results answer some open questions stated by Boutin.