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