0
$\begingroup$

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 ].
Improve this question
$\endgroup$
  • 1
    $\begingroup$ What is the definition of "complexity of a graph isomorphism"? $\endgroup$ – Moritz Jul 29 '15 at 9:42
  • $\begingroup$ @Moritz , time complexity of a graph isomorphism. $\endgroup$ – Michael Jul 29 '15 at 10:02
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ in question $m=n$ , also what is the best known bound, can u give link or paper containing results ? $\endgroup$ – Michael Jul 29 '15 at 9:59
  • $\begingroup$ What bound are you talking about? $\endgroup$ – Batominovski Jul 29 '15 at 10:01
  • $\begingroup$ I meant best time complexity $\endgroup$ – Michael Jul 29 '15 at 10:03
  • $\begingroup$ We still don't know what you mean by "time complexity." $\endgroup$ – Batominovski Jul 29 '15 at 10:04
  • 3
    $\begingroup$ Are you talking about the graph isomorphism problem? If so, then the time complexities for complete graphs and for symmetric complete bipartite graphs are both constant. Two complete graphs are isomorphic iff they have the same number of vertices, and likewise for the symmetric complete bipartite graphs. Even for all complete bipartite graphs, two are isomorphic iff they have the same bipartitions, whence also constant time complexity. $\endgroup$ – Batominovski Jul 29 '15 at 10:13
-1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.