Isomorphic Graphs

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 edges  iff  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).

REFERENCES

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. ACM 17, 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. ACM 23, 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.