Direct product of graphs $G$ and $H$ is a graph $G\times H$ for which

$V(G\times H)=V(G)\times V(H)$

$E(G\times H)=\left\{(g_1,h_1)(g_2,h_2):\ g_1g_2\in E(G),\ h_1h_2\in E(H)\right\}$.

Direct product is associative: $(G\times H)\times I\cong G\times (H\times I)$, so we can define direct product of $n$ graphs $G_1\times G_2\times\ldots G_n$.

There are some theorems about relations between automorphisms groups of Cartesian and Strong graph products and the automorphisms groups of it's factors (for example automorphism group of Cartesian product of relatively prime graphs is isomorphic to direct product of automorphism groups of these graphs).

We know that prime factorization of graph with respect to direct product is, in general, not uniqe and it can made some difficulties, but my question is:

Are there some known properties about relation between automorphisms group of direct product of graphs and the automorphisms group of its factors?

  • $\begingroup$ I'm pretty sure it's just going to be the direct product of the automorphism groups. $\endgroup$ – Jack M Jun 1 '14 at 21:56

The "bible" in these matters is Hammack R., Imrich W., Klavzar S., Handbook of product graphs, 2ed. They prove that the automorphism group of the direct product of pairwise coprime graphs is what you would expect, provided that the product itself is connected, not bipartite, and has no two vertices with the same neighbourhoods.

Rather define "what we would expect", I note that if $G$ and $H$ are coprime, then the automorphism group of $G\times H$ is the product of the automorphism group of its factors. If $G$ is prime, then the automorphism group of the product of $k$ copies of $G$ is the wreath product of $\mathrm{Aut}(G)$ by $\mathrm{Sym}(k)$.

Another formulation is that if the product satisfies the given condition, its automorphism group is the direct product of the automorphism group of its prime factors.

If the product is not connected etc., the automorphism group can be larger.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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