By a well-known result we know that a simply primitive permutation group of degree $2p$ where $p$ is a prime is $A_5$ or $S_5$ acting on 2-subsets of $\{1,\ldots,5\}$. The group has rank 3 and the orbital graph corresponding to the subdegree 3 is the Petersen graph with full automorphism group $S_5$. Is the left non-diagonal orbital graph a well-known graph? Is its full automorphism graph $A_5$? Generally is the Petersen graph (ignoring its complement) the only graph with 10 vertices with $S_5$ as its automorphism group? How many vertex-transive graph are with full automorphism group $A_5$ as a simply primitive group of degree 10?


Since $A_5$ has a single conjugacy class of subgroups of order $6$, it has a unique transitive action on 10 points (up to equivalence). This is the action on the vertices of the Petersen graph and it has only 3 suborbits, so the only graphs realising this action on vertices as automorphisms are the edgeless graph on 10 vertices, the Petersen graph, and their complements. Of course, in none of these cases is $A_5$ the full automorphism group.

$S_5$ has two conjugacy classes of subgroups of order $12$, so it has two non-equivalent transitive actions on 10 points. One is the action on the vertices of the Petersen graph (and again, there are 3 suborbits, so no other interesting graph arises). The other is the action of $S_5$ on the cosets of $A_4$. This one is imprimitive, with blocks of size 2 and 5. There are 4 sub-orbits, and depending on which choices you make, you get the edgeless graph, two copies of $K_5$, five copies of $K_2$ or two copies of $K_5$ joined by a perfect matching (or the complement of any of these). In any case, the full automorphism of the graph is bigger than $S_5$.

I don't know what you mean by "Is the left non-diagonal orbital graph a well-known graph?".

(Note, I performed some of the computations with magma, but you could also check Gordon Royle's data and use Sage, for example : http://school.maths.uwa.edu.au/~gordon/remote/trans/index.html).

  • $\begingroup$ Many thanks for your beautiful and exact answer. By your answer there is no vertex-transitive graph with full automorphism $A_5$ and only primitive graph with automorphism $S_5$ is the Petersen graph or its complement. $\endgroup$ – majid arezoomand Nov 26 '12 at 7:26

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.