The graph isomorphism problem is polynomial
| dc.creator | Golubchik, Aleksandr | |
| dc.date | 2006-07-29 | |
| dc.date | 2007-05-07 | |
| dc.date.accessioned | 2026-07-07T08:00:08Z | |
| dc.date.available | 2026-07-07T08:00:08Z | |
| dc.description | It is known that a graph isomorphism testing algorithm is polynomially equivalent to a detecting of a graph non-trivial automorphism algorithm. The polynomiality of the latter algorithm, is obtained by consideration of symmetry properties of regular $k$-partitions that, on one hand, generalize automorphic $k$-partitions (=systems of $k$-orbits of permutation groups), and, on other hand, schemes of relations (strongly regular 2-partitions or regular 3-partitions), that are a subject of the algebraic combinatorics. It is shown that the stabilization of a graph by quadrangles detects the triviality of the graph automorphism group. The result is obtained by lineariation of the algebraic combinatorics. Keywords: $k$-partitions, symmetry, algebraic combinatorics | |
| dc.description | 9 pages, Latex2e | |
| dc.identifier | https://arxiv.org/abs/math/0607770 | |
| dc.identifier | http://arxiv.org/abs/math/0607770 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/128605 | |
| dc.subject | General Mathematics | |
| dc.subject | 05C60, 05E99 | |
| dc.title | The graph isomorphism problem is polynomial | |
| dc.type | text |