Regular Graphs and Isomorphism I would like to ask whether there is an already published result on that:

We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and number of nodes $n$) graphs and write down their lengths. Of course this number of distinct paths is exponential. My  question is, if we sort the lengths and compare them (the lists obtained by the two graphs) and they are exactly the same, can we say that the two graphs are isomorphic?

Of course, even if this is a result we cannot use it to reply for Graph Isomorphism, since the number of distinct paths is exponential, as said

By distinct paths, I refer to paths having at least one different node, obviously.

Thanks in priori for your help.
I believe the answer to your question is "no" because an equivalent condition would imply a polynomial time solution to GI.

For $A$, the adjacency matrix of the graph $G$, note that the number of paths from $i$ to $j$ of length $k$ is $(A^k)_{i, j}$ (with repetition of vertices and edges allowed).  For two graphs $G_1$ and $G_2$ (with adjacency matrices $A_1$ and $A_2$) and $k \ge 1$, if you sorted the elements of $A_1^k$ and $A_2^k$ then in order for $G_1$ to be isomorphic to $G_2$, it is a necessary condition that the lists be identical for all $k$.

I believe your conjecture is equivalent to:

If the sorted lists of elements of $A_1^k$ and $A_2^d$ are identical for $k = 1$ to $n - 1$ (upperbound on the longest path with non-repeating vertices) then $G_1$ and $G_2$ are isomorphic.

So to solve GI, one only has to perform $n - 1$ multiplications of $n \times n$ matrices (and a little extra time to sort and compare $n^2$ elements).  This would take less than $n^4$ time.

I admit two possible flaws in my argument.  First, it is totally possible that GI has a polynomial time algorithm and that we just discovered it together, just now (hooray, we're famous!).  I find this highly unlikely.  Second (and much more probable), what I've proposed is not actually equivalent to your conjecture.

Final thought.  Have you tried this out for all, say, 3-regular graphs for size 8 or so?  I would think that if your conjecture is false, that there should be a counter example in 3-regular graphs of fairly small size.