RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1979 Volume 88, Pages 56–61 (Mi znsl3102)

This article is cited in 5 papers

Two reductions of graph isomorphism to problems for polynomials

D. Yu. Grigor'ev


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$).

UDC: 510.52+519.17


 English version:
Journal of Soviet Mathematics, 1982, 20:4, 2296–2298

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024