MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.