RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2016 Volume 22, Number 1, Pages 235–240 (Mi timm1275)

Reduction of the graph isomorphism problem to checking the equality of polynomials of $n$ variables

A. V. Prolubnikov

Omsk State University

Abstract: 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.

Keywords: graph isomorphism, complete invariant.

UDC: 519.178

Received: 26.12.2014



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025