Group generated by "adjacent" permutations of graph

Question

Let $G=(V,E)$ be any graph, i.e. $E$ is simply a binary relation over $V$. We say a permutation $\sigma\in \text{Bij}(V)$ of the vertices of $G$ is adjacent if, for all $v\in V$, $(v,\sigma(v))\in E$. Then the adjacency group of $G$, $A(G)$, is defined as the subgroup of $\text{Bij}(V)$ generated by the adjacent permutations of $G$.

Here are some examples.

$A(C_n^d)\cong \mathbb{Z}/n\mathbb{Z}$ where $C_n^d$ is the cyclic, directed, looped, graph of order $n$ (looped meaning that the identity permutation is adjacent).

If $G$ is finite, undirected, connected and looped, then $A(G)=\text{Bij}(V)$.

$A(C_4)\cong D_8$ where $C_4$ is the simple cyclic graph of order 4. $A(C_n)\cong \mathbb{Z}/n\mathbb{Z}$ for odd $n$ and, for even $n$, $A(C_n)$ blows up.

If $G$ and $H$ are looped then $A(G\sqcup H)=A(G)\times A(H)$. As a consequence, every finitely generated abelian group is the adjacency group of some graph.

My question is simple: is every (finite?) group the adjacency group of some graph?

Answer 1

No, you can't realize the quaternion group $Q$ of order 8 in this way.

Suppose that $Q$ acts on a graph $X=(V,E)$ in an adjacent and faithful way, and let us prove that the "adjacent group" of this graph contains an element of order 8. So there is a generating subset $S$ of $Q$ such that every element of $S$ is adjacent on $X$.

Let $u,v$ be two non-commuting elements of $S$ (so $u$, $v$ have order 4 and generate $Q$), and define $z=[u,v]$ (the generator of the center of $Q$, of order $2$). Let $x$ be a vertex not fixed by $z$, and let $Y$ be the $Q$-orbit of $x$. So $Y$ has cardinal 8 (otherwise $x$ would be fixed by $z$, since every proper subgroup of $Q$ contains $z$).

We have $Q=\{1,u,v,w,z,-u,-v,-w\}$, where $w=uv$, $-u=zu$ (etc.). So $Y=\{x,ux,zx,-ux,vx,wx,-vx,-wx\}$.

Define a permutation $s$ of $V$ as follows: $sy=uy$ for each $y\notin Y$, $s$ is defined on $Y$ as the following 8-cycle: $$x\stackrel{u}\mapsto ux\stackrel{v}\mapsto-wx\stackrel{u}\mapsto vx\stackrel{v}\mapsto zx\stackrel{u}\mapsto -ux\stackrel{v}\mapsto wx\stackrel{u}\mapsto -vx\stackrel{v}\mapsto x$$

(i.e. we alternatively apply $u$ and $v$ to $x$). So $s$ is an adjacent permutation of order 8, as required, and hence the subgroup generated by adjacent permutations is strictly larger than $Q$.