Take the 2-minute tour ×

Let $\Gamma$ be a Cayley graph over group $K$ and $H$ be a semiregular subgroup of $Aut(\Gamma)$ with two orbits. Then $|K|=2|H|$. Is there any other relation between $H$ and $K$ in general? What about special cases?

share|improve this question
In order to conclude that $|K|=2|H|" you should add WITH TWO ORBITS at the end of your first sentence. Now that your question has changed my earlier answer is not applicable and I have deleted it. –  Nick Gill Nov 11 '12 at 16:17

2 Answers 2

up vote 3 down vote accepted

In general, you can't say mauch. Take $\Gamma$ to be the complete graph $K_n$. Then $\Gamma$ is a Cayley graph for any group $K$ of order $n$, and any group $H$ of order $n/2$ acts semiregularly on $\Gamma$ with two orbits.

share|improve this answer
Ok. Thanks so much. Do you think may be any relation between this two subgroups in special cases? For example for (non-complete)Cayley graphs of order twice a prime? –  majid arezoomand Nov 20 '12 at 13:10

EDIT: I assumed that $H$ was a subgroup of $K$, which was not in the question.

No, there are no other relations: given a group $K$, a subgroup $H$ of index $2$ and a Cayley graph $\Gamma$ on $K$, it is always the case that $H$ is a semiregular subgroup of $Aut(\Gamma)$ with two orbits.

In fact, there is nothing special about $2$ here. If $\Gamma$ is a Cayley graph on $K$, then $K$ acts regularly on the vertices of $\Gamma$. In particular, any subgroup $H$ of $K$ will act semiregularly on the vertices, and the orbits of $H$ will simply be the cosets of $H$ in $K$. In particular, the number of orbits is the index of $H$ in $K$.

This all follows directly from the definitions and, as such, not really research level.

share|improve this answer
As you mentioned, if $|K:H|\geq 3$ then $H$ has at least 3 orbits and so 2 is neccesary here. –  majid arezoomand Nov 11 '12 at 19:00
There was a typo in the first part of my answer, which is now fixed. Again, I want to emphasise that there is almost no content in my answer and that this is all seen easily from the relevant from the definitions. –  verret Nov 11 '12 at 22:33
Majid didn't say that $H$ is a subgroup of $K$, only that $H$ is a subgroup of Aut($\Gamma$). The case where $H$ is not a subgroup of $K$ is the interesting case. –  Brendan McKay Nov 11 '12 at 23:36
You're right, I missed that. I'll edit. While I agree that this more general situation is more interesting, it's not really clear what is the question exactly. –  verret Nov 12 '12 at 0:13
I think that the question is clear. I want any relation between these two subgroups. –  majid arezoomand Nov 15 '12 at 18:21

Your Answer


