For the purposes of this question, all graphs are undirected and contain no loops.

Fix a non-negative integer $n$. Then we can see the automorphism group $\text{Aut}(G)$ of every graph $G$ with vertices $\{ 1,\dots,n \}$ as a subgroup of the symmetric group $S_n$. As is known, the intersection of any two subgroups is again a subgroup. This means that, for any two graphs $G_1$ and $G_2$ on $n$ vertices, the intersection $\text{Aut}(G_1) \cap \text{Aut}(G_2)$ is also a subgroup of $S_n$. Under what conditions is there a graph $G_3$ (also on $n$ vertices) such that $\text{Aut}(G_3) = \text{Aut}(G_1) \cap \text{Aut}(G_2)$ (again, as a subgroup of $S_n$)?

I'm aware of Frucht's theorem, but that construction in general does not guarantee the number of vertices remains the same.

For small graphs ($n \le 5$), it seems the above is possible for all subgroups except the trivial subgroup.

  • $\begingroup$ Indeed if $\Gamma$ is a graph such that $|\operatorname{Aut}(\Gamma)| = 1$, then $G$ has at least $6$ vertices. But also, if $\Gamma$ is a graph such that $|\operatorname{Aut}(\Gamma)| = 3$, then $G$ has at least $9$ vertices. See for example here. $\endgroup$ – spin Jan 17 at 19:34

I don't think there is an easy answer to this question. Finding which permutation groups are automorphism groups of graphs is actually not that easy. The fact that the trivial group does not arise for small graphs is already an indication of some of the difficulties.

I also think your claim that this is the only exception for $n\leq 5$ is false.

For example, for $n=4$, the Sylow $2$-subgroups are automorphism groups of graphs ($4$-cycles, for example) but if you intersect these, you get the normal subgroup of $S_4$ consisting of the identity and the double transposition. (Isomorphic to the Klein group.) This is not the automorphism group of a graph, as can easily be checked by hand. (The only graphs it preserves are the complete graph or a $4$-cycle or complements of these, so the full group is always bigger.)

If you are interested in this problem, the notion of "2-closure" of a permutation group is closely related.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.