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. UPD: according to the Wikipedia page, non-trivial minor-closed graph families can not represent all groups as symmetries, hence the family of graphs with treewidth $\leq k$ is not universal for any fixed $k$.
My questions are:
- Which growth rate of $k = k(|V|)$ is required for universal representability (that is, how relatively non-treelike the universal graphs should be)?
- Can we characterize the automorphism groups of bounded treewidth graphs for each threshold $k$ (along the lines of tree automorphism groups description above)?
