Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
    
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! –  Daniele Morelli Jul 21 '11 at 13:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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