The celebrated Frucht's theorem states that every finite group is isomorphic to the automorphism group of a finite graph $G$. If we restrict $G$ to belong to a certain class, some groups may become non-representable: e.g., automorphism groups of trees are the ones obtainable from the trivial group using direct product and wreath product with symmetric groups, and groups as small as $\mathbb{Z}_3$ can be non-representable this way.
In light of this, it is natural to ask if "tree-like" graphs are inherently unable to represent all groups. One possible formulation of this to consider graphs of bounded treewidth. My questions are:
- Is there a large enough $k$ so that all finite groups are automorphism groups of graphs with treewidth at most $k$? If no, which growth rate of $k = k(|V|)$ is required for universal representability?
- Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?