For every $k\in\Bbb N$ is it possible to find a graph $G$ on large enough $n\in\Bbb N$ vertices such that $\big|Aut(G)\big|=(n-k)!$? Is it possible to construct it quickly?



Graphs with prescribed Automorphism groups
For $k=0$, take a complete graph and for $k=1$, a star. For $k\geq 2$, take a path with $k$ vertices, and a complete graph with $n-k$ vertices, then join one end of the path with all the vertices in the complete graph.


It is not hard to see that the resulting graph has the required property. For large enough $n$, the other endpoint of the path is the unique vertex of degree $1$, so it is fixed. Then everything vertex on the path is also fixed, and clearly we can permute the vertices of the complete graph freely.


