Can any finite group be realized as the automorphism group of a directed acyclic graph?

Question

We are given a finite group $G$ and wish to find a DAG (directed acyclic graph) $(V,E)$ whose automorphism group is exactly G (a graph automorphism of a graph is a bijective function $f:V\to V$ such that $(u,v)\in E \iff (f(u),f(v))\in E$).

A similar (positive) result for undirected graph is known: Frucht's theorem.

My uneducated guess is that the answer to my question is negative, i.e. the automorphism groups of DAG's have some special properties. For directed trees the problem is very simple, and one can show that even $\mathbb{Z}_3$ is not realizable as the automorphism group of a directed tree. However, I can't find a counterexample for DAG's.

Answer 1

Given an undirected graph $X=(V,E)$ with automorphism group $G$, we form the direct graph $\hat{X}=(\hat{V},\hat{E})$ in the following way by setting $$\hat{V}=V\cup\{v_e|e\in E\}$$ $$\hat{E}=\{(v,v_{\{v,w\}})|v\in V,w\in V\}.$$

Clearly each $v\in V$ has zero indegree and outdegree at least zero and each $v\in\hat{V}\setminus V$ has indegree two and zero outdegree. It follows that $\hat{X}$ has no cycles and so is a DAG.

It should be clear that every automorphism $g$ on $X$ induces an automorphism $g$ on $\hat{X}$ by simply mapping $v$ to $g(v)$ and mapping $v_e$ to $v_{g(e)}$. Because the $v_{\{w_1,w_2\}}$ are 'trapped' between the vertices $w_1$ and $w_2$, it should also be clear that no new automorphisms can act on $\hat{X}$ as the image of $v_{\{w_1,w_2\}}$ is fully determined by the images of $w_1$, $w_2$ and a possible reordering of the edges in $E$ between $w_1$ and $w_2$, which is all taken in to account by the above induced action.

Answer 2

Let $G=\{g_1, \ldots, g_n\}$ be a finite group and let $\alpha,\beta\notin G$. Let $V=G\times(G\cup\{\alpha,\beta\})$ and add edges as follows: For each $g\in G$ add edges $$ (g,\alpha)\to(g,\beta)\to (g,g_1)\to\ldots\to (g,g_n)$$ and for each $g,h\in G$ add an edge $(gh,\alpha)\to (h,g)$. Note that the vertices $(x,\alpha)$ are precisely those with indegree $0$ and the $(x,\beta)$ are precisely those with indegree $1$. Also, only the $(g,\alpha)$ have outdegree $>1$. It follows readily that the automorphism group of $(V,E)$ acts on $G\times \{\alpha\}$ and does so faithfully. If an automorpshim maps $(g,\alpha)$ to $(h,\alpha)$ it must map $(g,y)$ to $(h,y)$ for all $y\in G\cup \{a,\beta\}$. Finally, if an autmorphism maps $(e,\alpha)$ to $(g,\alpha)$ (which has an edge to $(e,g)$) it must necessarily map $(h,\alpha)$ to $(gh,\alpha)$ because onl ythat has an edge to $(h,g)$, i.e. the automorphism group acts as the left multiplication on $G\times\{\alpha\}$. Since $(x,y)\mapsto(gx,y)$ is in fact an automorphism of the graph for each $g\in G$, the automorphism group is isomorphic to $G$.