Given two (simple, undirected, finite) graphs $G\_1 = (V\_1, E\_1)$ and $G\_2 = (V\_2, E\_2)$, let their automorphism groups be $Aut(G\_1)$ and $Aut(G\_2)$.


I'll recall that the cartesian product $G\_1 \times G\_2$ has vertex set $V\_1 \times V\_2$ , and two vertices $(a,b) , (x,y) \in V\_1 \times V\_2$ are adjacent iff $(a,x) \in E\_1$ and b=y, or $(b,y) \in E\_2$ and a=x.


My question is: does the problem of determining $Aut(G\_1 \times G\_2)$ in terms of $Aut(G\_1)$ and $Aut(G\_2)$ has a simple answer? May you suggest some bibliographic reference about this and related problems? Basic texts about graph theory usually barely define the automorphism group, and more algebraically-oriented texts i found did not wuite answered the question.


I tried to find a way to answer the question by myself, but i did not succeed. I'd like to know if the problem is really not-so-trivial, or if i'm simply not smart enough :)
Thanks in advance for any comment.



Automorphism group of the cartesian product of two graphs.
All you need is in W. Imrich, S. Klavzar: "Product graphs: structure and recognition".
John Wiley & Sons, New York, USA, 2000. See also: Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. "Graphs and their Cartesian Products". A. K. Peters (2008).


One issue is that the automorphism group of the Cartesian product of $G$ with itself
is not isomorphic to $\mathrm{Aut}(G) \times \mathrm{Aut}(G)$, but rather to the wreath product of $\mathrm{Aut}(G)$ by $\mathrm{Sym(2)}$. But essentially this is all that can go wrong. The basic issue is to show that if a graph is connected then it has a unique factorization as a Cartesian product of prime graphs. This fact goes back to
Sabidussi, G. (1960). "Graph multiplication". Math. Zeitschrift.(1960). 72: 446–457.


Prime factorization can fail if $G$ is not connected.


