Let $\Gamma$ be a vertex transitive graph with $4p$ vertices, where $p$ is an odd prime. Let $\Delta$ be an imprimitive block of length $p$ for the automorphism group of the graph. How can I prove that $\Gamma$ is isomorphic to the lexicographic product of a graph with 4 vertices and a graph isomorphic to the subgraph of $\Gamma$ on $\Delta$? I know that by one of C. Godsil's papers (On Cayley graph isomorphisms, Ars Comb. 1983) when $\Gamma$ is a Cayley graph over $\Bbb Z_{4p}$ and $\Delta$ is the support of a $p$-cycle, the result is true. Godsil claimed in her paper that this is an easy exercise. But unfortunately I cannot prove it. I guess that the proof of Godsil's claim can be useful to prove my claim.

  • 1
    $\begingroup$ I thought Chris Godsil was (at the time of writing of the referenced paper) of male gender. I don't know about now; if Chris prefers "she" and "her", that memo has yet to reach my desk. $\endgroup$ – The Masked Avenger Jul 26 '13 at 22:28
  • $\begingroup$ I think you must be missing a condition. If there is a $p$-cycle (i.e. one cycle of length $p$ and the rest fixed points) it is indeed an easy exercise, but I don't see why it should be true just from the presence of a block of size $p$. In fact it isn't true, take the cartesian product of a $p$-cycle and a $4$-cycle. $\endgroup$ – Brendan McKay Jul 27 '13 at 1:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.