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

Is there any simple graph $\Gamma$ with 16 vertices with full automorphism group $G$ such that $H\cong Q_8$ be a semiregular normal subgroup of $G$?

share|cite|improve this question
$Q_8$ has outer automorphisms of order 2. So you can extend $Q_8$ using such an automorphism, obtaining $G$ of order 16... I hope it is not your homework. :) – Dima Pasechnik Dec 25 '12 at 17:07
Thanks for your answer. Indeed I want to be $G$ as full automorphism group of a graph with 16 vertices. So I change my question. – majid arezoomand Dec 25 '12 at 19:45
up vote 3 down vote accepted

Here is an example.

Adjacency matrix:

$ \left[ \begin{array}{cccccccccccccccc} 0&1&1&0&1&1&1&0&0&0&0&0&0&0&0&0\\1&0&0&1&1&1&0&1&0&0&0&0&0&0&0&0\\1&0&0&0&0&0&1&0&1&1&1&0&0&0&0&0\\0&1&0&0&0&0&0&1&1&1&0&1&0&0&0&0\\1&1&0&0&0&0&0&0&0&0&1&0&1&0&1&0\\1&1&0&0&0&0&0&0&0&0&0&1&0&1&0&1\\1&0&1&0&0&0&0&0&0&1&0&0&1&1&0&0\\0&1&0&1&0&0&0&0&1&0&0&0&1&1&0&0\\0&0&1&1&0&0&0&1&0&0&1&0&0&0&0&1\\0&0&1&1&0&0&1&0&0&0&0&1&0&0&1&0\\0&0&1&0&1&0&0&0&1&0&0&0&0&0&1&1\\0&0&0&1&0&1&0&0&0&1&0&0&0&0&1&1\\0&0&0&0&1&0&1&1&0&0&0&0&0&1&1&0\\0&0&0&0&0&1&1&1&0&0&0&0&1&0&0&1\\0&0&0&0&1&0&0&0&0&1&1&1&1&0&0&0\\0&0&0&0&0&1&0&0&1&0&1&1&0&1&0&0 \end{array} \right]$

Neighbours of each vertex:

$ \begin{array}{c|ccccc} 1&2&3&5&6&7\\ 2&1&4&5&6&8\\ 3&1&7&9&10&11\\ 4&2&8&9&10&12\\ 5&1&2&11&13&15\\ 6&1&2&12&14&16\\ 7&1&3&10&13&14\\ 8&2&4&9&13&14\\ 9&3&4&8&11&16\\ 10&3&4&7&12&15\\ 11&3&5&9&15&16\\ 12&4&6&10&15&16\\ 13&5&7&8&14&15\\ 14&6&7&8&13&16\\ 15&5&10&11&12&13\\ 16&6&9&11&12&14 \end{array} $

It is a Cayley graph on the semidihedral group of order 16. In fact, it is a graphical regular representation, so the full automorphism group acts regularly on the vertices. Note that the semidihedral group of order 16 has a (normal) subgroup isomorphic to the quaternion group.

share|cite|improve this answer

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.