Abstract:
The problem of isomorphism of $n$-vertices graphs with weights on their edges possesses a full system of invariants which consists of $(n^2+1)$ polynomials of degree $\leq n^2$ (theorem 1). The proof of existence of such a system is not effective and is based on the primitive element theorem. Theorem 2 asserts that the graph isomorphism problem (or even the problem of divising the set of vertices of a graph $T$ on the domains of transitivity) can be reduced in polynomial time to the problem of decomposition of some univariable polynomial $f$ into irreducible multipliers over some field $F_T$ (the coefficients of $f$ depend only on
the number of vertices of $T$).