Graph Isomorphism of Complete Graph.

Question

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 ].

Answer 1

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.

Answer 2

Complete graphs, for isomorphism have constant complexity (time). In any way you can switch any 2 vertices, and you will get another isomorph graph. If you switch vertex A with B, conditions will be same for both, because both are connected with every other vertex. Daniel