Distinguishing Cartesian powers of graphs
Wilfried Imrich, Sandi Klavžar · Journal of Graph Theory · 2006
The distinguishing number D(G) of a graph is the least integer d such that there is a d-labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K2, K3 with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 (1), #N17] on powers of prime graphs, and results of Klavžar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2|H| − |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006