Graph Isomorphism

Let be the vertex set of a simple graph and its edge set. Then a graph isomorphism from a simple graph to a simple graph is a bijection such that iff (West 2000, p. 7).

If there is a graph isomorphism for to , then is said to be isomorphic to , written .

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.

Wolfram Web Resources