The distinguishing number of the augmented cube and hypercube powers

The distinguishing number of a graph G, denoted D(G), is the minimum number of colors such that there exists a coloring of the vertices of G where no nontrivial graph automorphism is color-preserving. In this paper, we answer an open question posed in Bogstad and Cowen The distinguishing number of the hypercube, Discrete Math. 283 (2004) 29-35] by showing that the distinguishing number of , the pth graph power of the n-dimensional hypercube, is 2 whenever 2<p<n-1. This completes the study of the distinguishing number of hypercube powers. We also compute the distinguishing number of the augmented cube AQ_n, a variant of the hypercube introduced in Choudum and Sunitha Augmented cubes, Networks 40 (2002) 71-84]. We show that D(AQ₁)=2; D(AQ₂)=4; D(AQ₃)=3; and D(AQ_n)=2 for n?4. The sequence of distinguishing numbers answers a question raised in Albertson and Collins An introduction to symmetry breaking in graphs, Graph Theory Notes N.Y. 30 (1996) 6-7].