Let V(G) be the vertex set of a simple graph and E(G) its edge set. Then a graph isomorphism from a simple graph G to a simple graph H is a bijection f:V(G)->V(H) such that u v element E(G) iff f(u) f(v) element E(H). If there is a graph isomorphism for G to H, then G is said to be isomorphic to H, written G≅H. There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. As a result, the special complexity class graph isomorphism complete is sometimes used to refer to the problem of graph isomorphism testing.

graph automorphism | graph isomorphism complete | isomorphic | isomorphic graphs | isomorphism