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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2016},
     volume = {22},
     number = {1},
     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
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
%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/

[1] Cai J-Y., Furer M., Immerman N., “An optimal lower bound on the number of variables for graph identification”, Combinatorica, 12:4 (1992), 389–410 | DOI | MR | Zbl

[2] Grigorev D.Yu., “Dva svedeniya izomorfizma grafov k zadacham o polinomakh”, Zapiski nauch. seminara LOMI, 88, Nauka, 1979, 56–61 | MR | Zbl

[3] Tsvetkovich D., Dub M., Zakhs Kh., Spektry grafov. Teoriya i primenenie, Nauk. Dumka, Kiev, 1984 | MR

[4] Seidel J.J., “Strongly regular graphs with $(-1,1,0)$ adjacency matrix having eigenvalue 3”, Lin. Alg. Appl., 1:2 (1968), 281–298 | DOI | MR | Zbl

[5] Lipton R.J., Vishnoi N.K., Zalcstein Z., CC Technical Report, GIT-CC-03-51(data obrascheniya: 07.09.2015), 2003 URL: https://smartech.gatech.edu/bitstream/handle/1853/6511/GIT-CC-03-51.pdf