Polynomial algorithm for graph isomorphism?

[Jarek Duda]

There are n^2 invariants for graphs, which can be computed in polynomial time - diagonal terms of n different powers of the adjacency matrix.
They tells the number of closed path from the vertex of given length - for example diagonal of second power gives degrees of vertexes (for unoriented graph). Higher powers describes vertex local topology deeper.
Now vectors of these invariants for different vertexes can be sorted lexicographically, giving n^2 invariants up to isomorphism.

So if these invariants doesn't agree for two graphs - the aren't isomorphic.
But question is if the invariants agree, they are isomorphic.
I've showed that it should be in generic case:
http://front.math.ucdavis.edu/0804.3615v1

I'm looking for a counterexamples - two non isomorphic graphs with the same invariants.
How to look for them? Maybe there are none?

thanks
Jarek Duda

[Jarek Duda ()]

Above invariants creates some blocking of vertexes with the same invariants - it's topological property.
There will be always vertexes which are indistinguishable - for which there is automorphism transforming one into the other (which are in the same orbit), the question is if our blocking is blocking into orbits? And if the invariants determine uniquely transitive graphs (all vertexes have the same invariants)?

To create more invariants for vertex(i), we can take non diagonal elements of powers of the matrix, and forget about their order - sort them lexicographically. We can make it even smarter - use already found blocking - to the description of neighbor j {((A^k)_ij):k} include also the number of its block. Thanks of it we can find better blocking ... use it to get better ... it will stabilize in polynomial time.
Finally we have all powers of adjacency matrix, but without exact permutation of terms inside some blocks. The permutation inside the block can be freely chosen, so we can assume that we know exactly the first lines of powers of the matrix for each block.

Finally we for example have: diagonal and the first line of powers of the matrix: n^2 + n(n-1) polynomial equations for elements of symmetric matrix ( n(n-1)/2 terms).
We know that there is solution. The question is if is always unique?

[Jarek Duda]

I though to search for counterexamples among cospectral graphs, Ted Spence and Gordon Royle advised me to check strongly regular graphs:
http://www.maths.gla.ac.uk/~es/srgraphs.html
And ... all of them are counterexamples to all algorithms I've proposed...
These invariants even doesn't recognize orbits for these graphs... they seem to be copletely resistant to combinatorial type invariants... which makes that I've started to doubt about that polynomial isomorphism is polynomial...