Searching Isomorphic Graphs
DOI:
https://doi.org/10.14738/tnc.55.3551Keywords:
graph, isomorphism, bijective mapping, isomorphic graphs, algorithm, graph isomorphism problemAbstract
To determine that two given undirected graphs are isomorphic, weconstruct for them auxiliary graphs, using the breadth-first search.
This makes capability to position vertices in each digraph with respect
to each other. If the given graphs are isomorphic, in each of them we
can find such positionally equivalent auxiliary digraphs that have the
same mutual positioning of vertices. Obviously, if the given graphs are
isomorphic, then such equivalent digraphs exist. Proceeding from the
arrangement of vertices in one of the digraphs, we try to determine the
corresponding vertices in another digraph. As a result we develop an
algorithm for constructing a bijective mapping between vertices of the
given graphs if they are isomorphic. The running time of the algorithm
equal toO(n5), where n is the number of graph vertices.
References
(1) Harary F. Graph Theory. Addison-Wesley, Reading, MA, 1969.
(2) West D.B. Introduction to Graph Theory, 2nd ed. Prentice Hall, Inc.,NJ, 2001.
(3) Varmuza K. Chemometrics in Practical Applications. Rijeka, Croatia:InTech, 2012. { 326 p.
(4) Dehmer M., Grabner M. newblock The Discrimination Power of Molecular Identification Num-bers Revisited. MATCH Commun. Math. Comput. Chem. { 2013. { V. 69. { No 3. { pp. 785{79.
(5) McKay B.D., Piperno A. Practical Graph Isomorphism. J. Symbolic Computation. { January 2014. { V. 60. { pp. 94{112.
(6) Wale N. and Karypis G. Comparison of descriptor spaces for chemical
compound re-trieval and classification. In Proceedings of the International Conference on Data Mining, pages 678{689, Hong Kong, 2006.
(7) Aho A. V., Hopcroft J. E., and Ullman J. D.. The design and analysis of computer algorithms. Addison-Wesley publishing company, N.Y., 1976. 13
(8) Garey M.R. and Johnson D.S.. Computers and Intractability.
W.H.Freeman and Company, San Francisco, 1979.
(9) Kukluk J. et al., Planar Graph Isomorphism, JGAA, 8(3) - 2004 - pp. 313{356.
(10) Babai L. Graph Isomorphism in Quasipolynomial Time. arXiv:1512.03547v1, 2015, 84 pages.
