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$?

  • 1
    $\begingroup$ $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. :) $\endgroup$ – Dima Pasechnik Dec 25 '12 at 17:07
  • $\begingroup$ 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. $\endgroup$ – majid arezoomand Dec 25 '12 at 19:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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