A distinguishing $r$-labeling of a digraph $G$ is a mapping $\lambda$ from the set of vertices#R##N#of $G$ to the set of labels $\{1,\dots,r\}$ such that #R##N#no nontrivial automorphism of $G$ preserves all the labels.#R##N#The distinguishing number $D(G)$ of $G$ is then the smallest $r$ for which $G$ admits a distinguishing $r$-labeling.#R##N#From a result of Gluck (David Gluck, Trivial set-stabilizers in finite permutation groups,#R##N#{\em Can. J. Math.} 35(1) (1983), 59--67),#R##N#it follows that $D(T)=2$ for every cyclic tournament~$T$ of (odd) order $2p+1\ge 3$.#R##N#Let $V(T)=\{0,\dots,2p\}$ for every such tournament.#R##N#Albertson and Collins conjectured in 1999#R##N#that the canonical 2-labeling $\lambda^*$ given by#R##N#$\lambda^*(i)=1$ if and only if $i\le p$ is distinguishing.#R##N##R##N#We prove that whenever one of the subtournaments of $T$ induced by vertices $\{0,\dots,p\}$#R##N#or $\{p+1,\dots,2p\}$ is rigid, $T$ satisfies Albertson-Collins Conjecture.#R##N#Using this property, we prove that several classes of cyclic tournaments satisfy Albertson-Collins Conjecture.#R##N#Moreover, we also prove that every Paley tournament satisfies Albertson-Collins Conjecture.
['Kahina Meslem', 'Éric Sopena']
On the Distinguishing Number of Cyclic Tournaments: Towards Albertson-Collins Conjecture