Distinguishing tournaments with small label classes
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 923-928
Antoni Lozano; Antoni Lozano. Distinguishing tournaments with small label classes. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 923-928. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a87/
@article{AMUC_2019_88_3_a87,
     author = {Antoni Lozano and Antoni Lozano},
     title = { Distinguishing tournaments with small label classes},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {923--928},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a87/}
}
TY  - JOUR
AU  - Antoni Lozano
AU  - Antoni Lozano
TI  - Distinguishing tournaments with small label classes
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 923
EP  - 928
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a87/
ID  - AMUC_2019_88_3_a87
ER  - 
%0 Journal Article
%A Antoni Lozano
%A Antoni Lozano
%T Distinguishing tournaments with small label classes
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 923-928
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a87/
%F AMUC_2019_88_3_a87

Voir la notice de l'article provenant de la source Comenius University

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.