3
$\begingroup$

I have problems to prove wheter a regular graph is vertex-transitive or not. For instance, consider the following examples: the generalized Petersen graphs $P_{2,7},\;P_{3,8}$ and the Folkman graph. For the three of them it is known wheter or not they are vertex-transitive, but it's never explained the reason. Of course you can always try to find an automorphism to prove wheter or not they're vertex-transitive, but I am curious if a more intuitive, and less time-consuming guideline exist.

One gets more confused because a priori the "general newbie rule" is that a regular graph is always vertex transitive.

$\endgroup$
  • $\begingroup$ Not all regular graphs are vertex transitive. See SemisymmetricGraph at mathworld or wikipedia $\endgroup$ – JMoravitz May 21 '15 at 19:26
1
$\begingroup$

For generalized Petersen graphs it's easy to construct required automorphisms - there are obvious rotational symmetries taking any outer vertex to any other outer vertex, and any inner vertex to any other inner vertex; and there is the "turning inside out" symmetry which takes the inner "star" to the outer regular polygon; compositions of these show that the graph is vertex transitive.

For Folkman graph an easy proof would be to see that if you look at the 4 immediate neighbours of a vertex v, in half the cases all of them are connected to another vertex distinct from v, and in half the cases this is not so. Thus there is no automorphism exchanging these two types of vertices (this is a simple-minded version of an approach Folkman used in his paper, and can be fairly easily generalized a bit).

A regular graph is not even edge transitive, as a rule, starting with disconnected 2-regular graphs. Even if you consider connected ones, in 3-regular graphs you can replace an edge with a -(|)- and get a new 3 regular graph. I think doing it repeatedly in random places would yield fairly non-symmetric things. An interesting question whether one can prove that a random connected regular graph is not edge-transitive...

$\endgroup$
  • $\begingroup$ Can you argue for the Folkman graph that, because it is bipartite, vertex-transitivity fails when one does an automorphism between members of different partitions? $\endgroup$ – user2820579 May 22 '15 at 0:54
  • $\begingroup$ I think by "vertex-transitivity fails when one does an automorphism between members of different partitions" you mean that there is in fact no automorphism taking a vertex in one of the partitions to a vertex in the other partition. That is true for Folkman graph - as the argument above shows, but it's not generally true for bipartite graphs. $\endgroup$ – Max May 22 '15 at 7:17

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.