Basic results concerning the automorphism group of the tensor product of two graphs

Abstract

The tensor product of two graphs has an automorphism group determined in part by the groups of the underlying graphs. It is not hard to see that the group of the product contains the direct product (cartesian product) of the groups of the underlying graphs; sometimes the group is larger than this. There are a number of unexpected structural properties of graphs that ensure additional automorphisms of the product graph exist. This paper proves that these properties suffice, and characterizes some of the groups of the products of graphs satisfying these properties. The wreath product of permutation groups arises in a natural way in many such products.