[01] Anatoly Dmitrievich Plotnikov, Department of Information Systems Safety, Dalh East-Ukrainian National University, Severodonetsk, Ukraine.

The methodology of positioning graph vertices relative to each other to solve the problem of determining isomorphism of two undirected graphs is developed. Based on the position of the vertex in one of the graphs, it is determined the corresponding vertex in the other graph. For the selected vertex of the undirected graph, define the neighborhoods of the vertices are defined. Next, it is constructed the auxiliary directed graph, spawned by the selected vertex. The vertices of the digraph are positioned by special characteristics — vectors, which locate each vertex of the digraph relative the found neighborhoods. This enabled to develop the polynomial-time algorithm for determining graph isomorphism.

Isomorphism, Algorithm, Graph, Graph Isomorphism Problem

[01] Harary F. Graph Theory, Addison-Wesley, Reading, MA, 1969. [02] West D. B. Introduction to Graph Theory, 2nd ed. Prentice Hall, Inc., NJ, 2001. [03] Varmuza K. Chemometrics in Practical Applications. – Rijeka, Croatia: InTech, 2012. – 326 p. [04] Dehmer M., Grabner M. The Discrimination Power of Molecular Identification Num-bers Revisited // MATCH Commun. Math. Comput. Chem. – 2013. – V. 69. – № 3. – pp. 785–79. [05] McKay B. D., Piperno A. Practical Graph Isomorphism // J. Symbolic Computation. – January 2014. – V. 60. – pp. 94–112. [06] 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. [07] Aho A. V., Hopcroft J. E., and Ullman J. D. The design and analysis of computer algorithms. Addison-Wesley publishing company, N. Y., 1976. [08] Garey M. R. and Johnson D. S. Computers and Intractability. W. H. Freeman and Company, San Francisco, 1979. [09] 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.