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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.