The determining number of a Cartesian product |
| |
Authors: | Debra L Boutin |
| |
Institution: | Department of Mathematics, Hamilton College, Clinton, New York 13323 |
| |
Abstract: | 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 □?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G )}. 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(Qn)=?log2n?+1 which matches the lower bound, and that Det(K )=?log3(2n+1)?+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(Hn)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory |
| |
Keywords: | determining set graph automorphism |
|
|