Geodesic
Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 1, pp. 235-240

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that two graphs are isomorphic if there exists an enumeration for vertices of one of the graphs such that modified characteristic polynomials of the graphs are equal. An algorithm for solving the graph isomorphism problem is presented. The algorithm finds an enumeration for vertices of one of the graphs that provides the equality of coefficients of the polynomials if such an enumeration exists.
Mots-clés : graph isomorphism
Keywords: complete invariant. 
@article{TIMM_2016_22_1_a21,
     author = {A. V. Prolubnikov},
     title = {Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {235--240},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a21/}
}
TY  - JOUR
AU  - A. V. Prolubnikov
TI  - Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2016
SP  - 235
EP  - 240
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a21/
LA  - ru
ID  - TIMM_2016_22_1_a21
ER  - 
%0 Journal Article
%A A. V. Prolubnikov
%T Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables
%J Trudy Instituta matematiki i mehaniki
%D 2016
%P 235-240
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a21/
%G ru
%F TIMM_2016_22_1_a21
A. V. Prolubnikov. Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 22 (2016) no. 1, pp. 235-240. http://geodesic.mathdoc.fr/item/TIMM_2016_22_1_a21/