9
$\begingroup$

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.

$\endgroup$

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much, i'll look for those books! If i'm not wrong, when dealing with more than one component (Say, $G_1, ..., G_k$ distinct components with multeplicity $m_1, ..., m_k$) there should be a formula like $Aut(G) = Aut(G_1) * S_{m_1} \times ... \times Aut(G_k) * S_{m_k}$ Where $*$ is the wreath product (i have to check that, anyway), so one should be able to restrict its focus on single components. Thank you again! $\endgroup$ Jul 21, 2011 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.