The cost of 2-distinguishing Cartesian powers (Q1953468)

Summary: 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 label classes. The minimum size of a label class in any such labeling of \(G\) is called the cost of 2-distinguishing \(G\) and is denoted by \(\rho(G)\). The determining number of a graph \(G\), denoted \(\det(G)\), is the minimum size of a set of vertices whose pointwise stabilizer is trivial. The main result of this paper is that if \(G^k\) is a 2-distinguishable Cartesian power of a prime, connected graph \(G\) on at least three vertices with \(\det(G)\leq k\) and \(\max\{2, \det(G)\} < \det(G^k)\), then \(\rho(G^k) \in \{\det(G^k), \det(G^k)+1\}\). In particular, for \(n\geq 3, \rho(K_3^n)\in \{ \left\lceil {\log_3 (2n+1)} \right\rceil+1, \left\lceil {\log_3 (2n+1)} \right\rceil+2\}\).