Title of article :
Symmetry Breaking in Tournaments
Author/Authors :
Lozano، نويسنده , , Antoni، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Abstract :
We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S ⊆ V ( T ) is a determining set for a tournament T if every nontrivial automorphism of T moves at least one vertex of S, while S is a resolving set for T if every two distinct vertices in T have different distances to some vertex in S. We show that the minimum size of a determining set for an order n tournament (its determining number) is bounded by ⌊ n / 3 ⌋ , while the minimum size of a resolving set for an order n strong tournament (its metric dimension) is bounded by ⌊ n / 2 ⌋ . Both bounds are optimal.
Keywords :
metric dimension , Symmetry breaking , tournaments , determining number
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics