12
$\begingroup$

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?

$\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 Martínez Apr 14 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 Zaimi Apr 14 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. Smith Apr 14 at 20:59
9
$\begingroup$

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.

$\endgroup$

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.