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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Daniele Morelli
    Commented Jul 21, 2011 at 13:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .