The Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. Is it the "Cayley graph" of some slightly more general group-like structure?
$\begingroup$
$\endgroup$
3
-
4$\begingroup$ I don't know if you're interested, but it is the Schützenberger graph of an inverse semigroup. However, that might be overkill, as every undirected graph appears as a Schützenberger graph of an inverse semigroup. $\endgroup$– Diego MartinezApr 14, 2021 at 10:02
-
4$\begingroup$ Perhaps you are looking for the definition of a Schreier coset graph. These are like Cayley graphs but they are defined for quotients $G/H$. Every vertex-transitive graph can be written as a coset graph. en.wikipedia.org/wiki/Schreier_coset_graph $\endgroup$– Gjergji ZaimiApr 14, 2021 at 10:44
-
2$\begingroup$ It depends, of course, on what one means by "group-like". I want to echo the comment by Gjergjii Zaimi. The symmetric group $S_5$ is vertex transitive on the vertices of the Cayley graph and so we may create a graph with vertices defined not be single elements of the group but by cosets. Pick the stabilizer of a vertex and create a graph on those 10 cosets ... and one can recover the Petersen graph as a vertex of cosets, instead of singletons. $\endgroup$– Ken W. SmithApr 14, 2021 at 20:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
We are working on these questions currently with Ignacio Garcia-Marco. As a postive answer I can tell you that the multiplication table of S codes a semigroup. If you take elements 1,6 as connection set, then the right Cayley graph is Cay(S,{1,6}). Its underlying undirected simple graphs is the Petersen graph. From the negative side we can also show, that any directed Cayley graph (of a semigroup) whose underlying undirected simple graph is the Petersen graph has loops.
-
2$\begingroup$ so, we finally wrote down our paper on Generalized Petersen Graphs that are Cayley Graphs: arxiv.org/abs/2202.06785 $\endgroup$ Feb 16, 2022 at 15:51
$\begingroup$
$\endgroup$
2
For another positive answer you could have a look at Georgakopoulos & Wendland - Presentations for vertex-transitive graphs. This paper defines a notion of "partite group presentation", giving rise to "partite Cayley graphs", of which the Petersen graph is the first example. The idea is to allow different vertices to obey different relators. You may also find the notion of bi-Cayley graph relevant.
-
$\begingroup$ Interesting, can you express all the Generalized Petersen Graphs like this? The smallest one for which we do not know if it is the underlying graph of a Cayley Graph of a semigroup is G(7,2)... $\endgroup$ Jun 9 at 10:20
-
$\begingroup$ @KoljaKnauer: Yes, a partite presentation for $G(n,k)$ is $<{a}, {}, {b} | {a^n, aba^kb, b^2}, {a^n}>$. $\endgroup$– AgelosJun 13 at 10:36