%A Lozano, Antoni
%D 2019
%T Distinguishing tournaments with small label classes
%K
%X 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 ) ≤ 7 n /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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1219
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 923-928%V 88
%N 3
%@ 0862-9544
%8 2019-07-30