The Determining Number of a Cartesian Product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G = G(i)(ki) square ... square Gk(m)(m) is the prime factor decomposition of a connected graph then Det(G) = max{Det(G(i)(ki))}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q(n)) = inverted right perpendicularlog(2)ninverted left perpendicular + 1 which matches the lower bound, and that Det(K(3)(n)) = perpendicularlog(3)(2n+1)inverted left perpendicular + 1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(H(n)) = Theta(log n). (C) 2009 Wiley Periodicals, Inc. J Graph Theory 61: 77-87, 2009