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.

REFERENCES

Du, D.-Z. and Ko, K.-I. Theory of Computational Complexity. New York; Wiley, p. 117, 2000.

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-156, 1983.

McKay, B. "Practical Graph Isomorphism." Congr. Numer. 30, 45-87, 1981.

Skiena, S. "Graph Isomorphism." §5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.