Maximum number of isomorphic graphs

Question

Given a simple graph on $n$ vertices, how many graphs are atmost there that are isomorphic to the given graph? Is it $\Theta(n^2!)$ or $\Theta(n!)$ which is number of permutations of rows or columns?

Answer 1

The answer is exactly $n!$, no $\Theta$ required. Every other isomorphic graph is uniquely determined by an isomorphism, which is a bijective function from the set of vertices to itself. There are $n!$ such functions.

Answer 2

Let $V=\{1,\ldots,n\}$ and let $G$ be a graph on vertex set $V$. I assume you are asking for the number of graphs on vertex set $V$ that are isomorphic to $G$. The symmetric group $S_n$ acts on all graphs on vertex set $V$. We shall apply the orbit-stabilizer lemma. The number of graphs on $V$ isomorphic to $G$ is the size of the orbit of $G$ in this action. The stabilizer of $G$ is the automorphism group of $G$, which we shall denote by $Aut(G)$. By the orbit stabilizer lemma, the order of the group $S_n$ is the product of the size of the orbit of $G$ and the size of the stabilizer. Hence, the size of the orbit is $n!/|Aut(G)|$.