TOPICS
Search

Graph Isomorphism

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 uv in E(G) iff f(u)f(v) in E(H) (West 2000, p. 7).

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.

See also

Graph Automorphism, Graph Isomorphism Complete, Isomorphic, Isomorphic Graphs, Isomorphism

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Graph Isomorphism

Cite this as:

Weisstein, Eric W. "Graph Isomorphism." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphIsomorphism.html

Subject classifications