# Graph Isomorphism of Complete Graph.

what Is the complexity(computational complexity) of graph isomorphism of

1.Complete graphs($K_n$) and

2.Utility graphs (Complete bipartite graphs ,$K_{n,n}$)?

is it in polynomial ?

Looks like trivial case, looking for results. Thanks.

Edition :

1. "polarized graphs" isomorphism is a GI-complete problem (made of a complete graph $K_m$ and an empty graph $K_n$ plus some edges connecting the two; their isomorphism must preserve the partition)[Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I. (1985), "Graph isomorphism problem", Journal of Mathematical Sciences 29 (4): 1426–1481 ].
• What is the definition of "complexity of a graph isomorphism"? – Moritz Jul 29 '15 at 9:42
• @Moritz , time complexity of a graph isomorphism. – Michael Jul 29 '15 at 10:02

For $m,n\in\mathbb{N}$, $\text{Aut}\left(K_n\right)\cong S_n$ and, if $m \neq n$, $\text{Aut}\left(K_{m,n}\right) \cong S_m\times S_n$, whereas $\text{Aut}\left(K_{n,n}\right)\cong C_2\times S_n^2$, where $C_k$ and $S_k$ are the cyclic group of order $k$ and the symmetric group on $k$ elements, respectively. If your complexity is the size of the automorphism group, then the complexity is definitely not in polynomial. If your complexity is the size of a minimal generating set of the automorphism group, then the complexity is constant.
• in question $m=n$ , also what is the best known bound, can u give link or paper containing results ? – Michael Jul 29 '15 at 9:59