Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs
and with graph vertices are said to be isomorphic if there is a permutation of such that is in the set of graph edgesiff is in the set of graph
edges .
Canonical labeling is a practically effective technique used for determining graph isomorphism. Several software implementations
are available, including nauty (McKay), Traces (Piperno 2011; McKay and Piperno 2013),
saucy, and bliss, where the latter two are aimed particularly at large sparse graphs.
The equivalence or nonequivalence of two graphs can be ascertained in the Wolfram Language using the command IsomorphicGraphQ[g1,
g2].
Determining if two graphs are isomorphic is thought to be neither an NP-complete problem nor a P-problem, although this has not been proved (Skiena 1990,
p. 181). In fact, there is a famous complexity class called graph
isomorphism complete which is thought to be entirely disjoint from both NP-complete
and from P.
A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant
(Luks 1982; Skiena 1990, p. 181).
In some sense, graph isomorphism is easy in practice except for a set of pathologically difficult graphs that seem to cause all the problems. So, unlike knot theory, there
have never been any significant pairs of graphs for which isomorphism was unresolved.
In fact, for many years, chemists have searched for a simple-to-calculate invariant
that can distinguish graphs representing molecules. There are entire sequences of
papers in which one author proposes some invariant, another author provides a pair
of graphs this invariant fails to distinguish, and so on. Unfortunately, there is
almost certainly no simple-to-calculate universal graph invariant, whether based
on the graph spectrum or any other parameters of
a graph (Royle 2004).
Chartrand, G. "Isomorphic Graphs." §2.2 in Introductory
Graph Theory. New York: Dover, pp. 32-40, 1985.Corneil,
D. G. and Gottlieb, C. C. "An Efficient Algorithm for Graph Isomorphism."
J. ACM17, 51-64, 1970.Cvetković, D. M.; Doob,
M.; and Sachs, H. Spectra
of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.Harary,
F. Graph
Theory. Reading, MA: Addison-Wesley, pp. 10-11, 1994.Hopcroft,
J. E. and Tarjan, R. E. "A Algorithm for Isomorphism of Triconnected Planar Graphs."
J. Comput. Sys. Sci.7, 323-331, 1973.Hopcroft, J. E.
and Wong, J. K. "Linear Time Algorithm for Isomorphism of Planar Graphs
(preliminary Report)." In STOC '74: Proceedings of the Sixth Annual ACM Symposium
on Theory of Computing. New York: ACM, pp. 172-184, 1974.Junttila,
T. A. and Kaski, P. "bliss." http://www.tcs.hut.fi/Software/bliss/.Kocay,
W. "On Writing Isomorphism Programs." In Computational and Constructive
Design Theory. pp. 135-175, 1996.Luks, E. M. "Isomorphism
of Graphs of Bounded Valence Can Be Tested in Polynomial Time." J. Comput.
System Sci.25, 42-49, 1982.McKay, B. "nauty and Traces."
http://cs.anu.edu.au/~bdm/nauty/.McKay,
B. "Practical Graph Isomorphism." Congr. Numer.30, 45-87,
1981. http://cs.anu.edu.au/~bdm/nauty/pgi.pdf.McKay,
B. and Piperno, A. "nauty and Traces." http://pallini.di.uniroma1.it.McKay,
B. and Piperno, A. "Practical Graph Isomorphism, II." 8 Jan 2013. http://arxiv.org/abs/1301.1493.Piperno,
A. "Search Space Contraction in Canonical Labeling of Graphs." 26 Jan 2011.
http://arxiv.org/abs/0804.4881.Royle,
G. "Re: Inverting graph spectra." GRAPHNET@listserv.nodak.edu
posting. Oct. 29, 2004. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0410&L=graphnet&T=0&P=1933.Schmidt,
D. C. and Druffel, L. E. "A Fast Backtracking Algorithm to Test Directed
Graphs for Isomorphism Using Distance Matrices." J. ACM23, 433-445,
1976.Skiena, S. "Graph Isomorphism." §5.2 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 181-187, 1990.