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.

  • 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

1

Well, the fact that you haven't gotten an affirmative answer despite this question receiving many votes and views, is your meta-answer right there. You must assume that NO, "semi-direct product" for graphs has NOT been defined.

Even if someone at some point defined "semi-direct product" for graphs, you should assume that the definition didn't stick. Keep in mind that many people studying graph theory know little about group theory.

Given two graphs $G$ and $H$ there are many different types of graph products, if you are writing a paper then you are best just to explicitly describe the edge-set outright given $G$ and $H$ and if it looks reminiscent of something from algebra, then name it appropriately.

In fact, I would even go so far to say that if you use the term in writing a paper for a research journal, that you should explicitly define what you mean by a "Cayley graph".