15
$\begingroup$

The first subquestion is "has a standard notion of semidirect product been defined in graph theory"? If yes, i'd like to know if the definition i'm gonna give is equivalent to the standard one. I'd also like to know if there's some litterature about it. If the answer was "no", would you accept my definition as a reasonable "semidirect product"?

Consider two graphs $G$ and $H$ (finite, undirected, simple, loopless, and of order $n,m$ respectively), and let $Aut(H)$ denote the set of automorphisms of $H$. Pick $\phi_1, ..., \phi_n \in Aut(H)$, and construct a semidirect product as follows:

Label the elements of $G$ as $1,2,...,n$. Pick $n$ copies $H_1, ..., H_n$ of $H$. If $x_i \in H_i$ and $x_j \in H_j$, add an edge between them iff $(i,j) \in E_G$ and $\phi_i(x_i)= \phi_j(x_j)$. The result of this operation is the semidirect product $G \ltimes_{(\phi_1, ..., \phi_n)} H$

I hope this is clear... In other words, you perform a simple cartesian product, but you tilt each "$H$" component using an automorphism before connecting the respectives fibers. As an exemple, consider the Petersen graph as a semidirect product of $K_2$ and $C_5$ (where we can choose the identity and a nontrivial automorphism):

Let $G = K_2$ and let $H=H_1=H_2$ be the cycle $a - b - c - d - a$ (dashes mean adiacency. Also let $\phi_1, \phi_n$ be automorphisms in $Aut(H)$ defined as:

$\phi_1 = Id$

$\phi_2(a)=a; \phi_2(b)=c; \phi_2(c)=e; \phi_2(d)=b; \phi_2(e)=d;$

Following the definition we will add an edge between:

$a \in H_1$ and $a \in H_2$ as $a = \phi_1(a) = \phi_2(a) = a$

$b \in H_1$ and $d \in H_2$ as $b = \phi_1(b) = \phi_2(d) = b$

$c \in H_1$ and $b \in H_2$ as $c = \phi_1(c) = \phi_2(b) = c$

$d \in H_1$ and $e \in H_2$ as $c = \phi_1(d) = \phi_2(e) = d$

$e \in H_1$ and $c \in H_2$ as $c = \phi_1(e) = \phi_2(c) = e$

Thanks for reading. Feedback would be really appreciated.

  • 2
    Why do you expect this do be a good notion of semidirect product? Which are the properties you would like a semidirect product of graphs to satisfy?2011-11-21
  • 1
    Are your "automorphisms" supposed to to preserve the edges of each $H_i$, or are they just arbitrary permutations of the vertices? The latter would seem to be necessary for your Petersen graph example to work. But in that case I think it is stretching it to call them automorphisms in the first place -- certainly they are not graph isomorphisms $H\to H$.2011-11-21
  • 2
    Possibly the zig-zag product? http://en.wikipedia.org/wiki/Zig-zag_product It has some relation to semidirect products, as discussed here: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/ALW01/proc.pdf2011-11-21
  • 0
    Thanks for answering. I'll try to better explain my Petersen graph exemple: the "inner" (star) and the "outer" (penthagon) paths in Petersen graph are both isomorphic to $C_5$. So one may actually define a proper, edge-preserving automorphism in $Aut(C_5)$ so that the definition makes sense. If $H=C_5$, then $H_1=H$ is the cycle $a \to b \to c \to d \to e \to a$. For exemple suppose $\phi(a)=a$, then $H_2$ is the cycle $a \to c \to e \to b \to d \to a$. One may easily write the complete behaviour of $\phi$ this way.2011-11-21
  • 0
    @Daniele, if I understand you correctly, the spokes are supposed to connect $\phi^{-1}_1(a)\in H_1$ with $\phi^{-1}_2(a)\in H_2$ and $\phi^{-1}_1(b)\in H_1$ with $\phi_2^{-1}(b)\in H_2$. However, since $a\leftrightarrow b$ is an edge in $H$, being edge-preserving means that there are _also_ edges $\phi_1^{-1}(a)\leftrightarrow\phi_1(b)^{-1}$ in $H_1$ and $\phi_2^{-1}(a)\leftrightarrow\phi_2^{-1}(b)$ in $H_2$. This creates a 4-cycle, of which there are none in the Petersen graph.2011-11-23
  • 0
    If I have misunderstood something, perhaps you could edit your question to include a _fully concrete_ example, showing the _precise_ permutations you're using and the _precise_ labelings of each vertex in the result?2011-11-23
  • 1
    Thanks for your interest, i'm gonna edit the question (i'm not very good at formalizing concepts, have mercy :) )2011-11-23
  • 1
    @DanieleMorelli: φ2 is not an automorphism of H, since a - b is an edge of H but φ2(a) - φ2(b) is not an edge of H.2011-11-23
  • 0
    AAh i see now. You people are totally right... Then I should write, for exemple, Sym(V_H) instead of Aut(H)... i suppose. Thanks for your constructive critics, i'll be back if something interesting comes out. (You may consider the question answered if you wish)2011-11-24
  • 0
    If you haven't already, I would suggest that you watch this short video by Nathan Carter about how to visualize the semidirect product. It might give you some inspiration on how to achieve this for general graphs, instead of Cayley graphs. https://www.youtube.com/watch?v=MnRcc9eINaQ2017-02-25

1 Answers 1