3
$\begingroup$

From theorem $4$ and corollary $1$ in this book we have that graph isomorphism has to do with automorphism group of a graph. We also know every group is the automorphism group of a graph by Frucht's theorem. However here I seek something stronger. I want to fix the size of graphs I seek automorphism group.

Given integer $m$ from $1$ to $n$

  1. how many non-isomorphic subgroups of order $m$ can occur as automorphism group of a graph of size $n$?

  2. How many distinct subgroups of $S_n$ can occur as automorphism groups of a graph of size $n$?

Is there an easy way to understand 1. and 2. as I am only looking for asymptotics?

  1. What is the minimum $f(n)$ needed to realize all distinct subgroups of $S_n$ as automorphism group of some graph of size $f(n)$?

  2. Do any of 1.,2. and 3. change significantly if we are allowed directed graphs?

Improve this question
$\endgroup$
2
  • $\begingroup$ for 2., take the complete graph $K_n$. Then every subgroup of $S_n$ is its automorphism group. $\endgroup$
    – Dima Pasechnik
    May 29, 2019 at 9:44
  • $\begingroup$ What do you mean by 'automorphism group'? Do you mean the group of all automorphisms of the graph? If so, only $S_n$ counts as the automorphism group of $K_n$. $\endgroup$
    – Michael Giudici
    Jun 11, 2019 at 14:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.