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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Instead of path, any graph with trivial automorphism group will do, right? $\endgroup$– joroCommented Aug 14, 2016 at 6:57
-
$\begingroup$ Yes, another possibility is to use the disjoint union of a complete graph with a graph with trivial automorphism group, but that doesn't work for $k\in\{2,3,4,5\}$. $\endgroup$– verretCommented Aug 14, 2016 at 7:04