Small label classes in 2-distinguishing labelings - Boutin, Debra L. (Ars mathematica contemporanea, 2008)
A graph ?$G$? is said to be 2-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of ?$G$? the cost of 2-distinguishing ?$G$? and denote it by ?$ρ(G)$?. This paper shows that for ?$n \ge 5$?, ?$\lceil \log_2 n\rceil + 1 \le ρ(Q_n) \le 2\lceil \log_2n \rceil - 1$?, where ?$Q_n$? is the hypercube of dimension ?$n$?.
Keywords: grafi; matematika; teorija grafov