Surprised to know there are two $O(n^3)$ isomorphic algorithms for simple and undirected graphs based on distance matrix.
DOI 10.16383/j.aas.c230025. Wang Zhuo, Wang Cheng-Hong "Isomorphism determination methods for simple undirected graphs", Acta Automatica Sinica, 2023, 49(9): 1878-1888
After read it carefully, a much simpler method is invented based on $$ Fg :=Ag + M + r \cdot I $$ where
- $Ag$ is the adjacency matrix,
- $M$ is a $n\times n$ matrix whose entries are equal to $m$
- $I$ is the identity matrix,
- $m$, $r$ are free variables.
Under the above conditions, then $$ \det(Fg) = \det(Fh) \iff g\text{ and }h\text{ are isomorphic.} $$ Note that
- this is true for all undirected graphs (except for one unknown case: $g$ has different number loop for nodes).
- It's similar to Jones polynomial generalized to HOMFLY for knot theory (by introducing a second variable $m$).
Though it is strong, but for digraphs, it is not always true even with more constrains.
