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.
Best Answer
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.