Generalized Cayley graphs were introduced by Marusic etal in 1992. Ademir Hujdurovic etal proved that there are infinitely many vertex-transitive generalized Cayley graphs which are not Cayley graphs. In fact, line graph of Petersen graph is one such example. They also prove that generalized Cayley graphs admits semi-regular automorphism.

It is obvious generalized Cayley graph $GC(G,S,\alpha)$ is $|S|$-regular. Moreover, there are examples of non-vertex-transitive generalized Cayley graphs.

My question is: Does there exist any vertex-transitive graph which is not generalized Cayley?

One answer to this is Petersen graph. For if it is generalized Cayley graph of order $10$ ($=2p$), it must be Cayley.

I am looking for some more such examples?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.