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

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.

Surprised to know there are two $O(n^3)$ isomorphic algorithms for simple and undirected graphs based on distance matrix.

DOI is 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 :=$ adjacency matrix $Ag$ $+ M$ (matrix with n * n element m) + $r *$ Identity matrix； m, r are free variables, then $det(Fg) = det(Fh) <==> g$ and $h$ are isomorphic. It 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 introduce second variable m). Though it is strong, but for digraphs, it is not always true even with more constrains.

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