Main Article Content
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.
How to Cite
Lozano, A. (2019). Distinguishing tournaments with small label classes. Acta Mathematica Universitatis Comenianae, 88(3), 923-928. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1219/744