graph isomorphism

A graph isomorphism is an isomorphism between two graphs \(G\) and \(H\) meaning that there exists \(f\) a bijection between the vertexes of \(G\) and those of \(H\) such that \((u, v)\) is an edge in \(G\) if and only if \((f(u), f(v))\) is an edge in \(H\).

Weisfeiler-Lehman algorithm

This algorithm computes an approximation of the graph isomorphism, but it has good properties on simple graph. In fact, it is more a family of algorithms parameterized by an integer \(k > 0\), each algorithm is denoted by $k$-WL.

I think that the following properties are correct:

  • 1-WL is able to find the isomorphisms between the trees,
  • 3-WL is able to find the isomorphisms between the planar graph.

This post accepts webmentions. Do you have the URL to your post?

Otherwise, send your comment on my service.

Or interact from the fediverse with your username:

fediverse logo Share on the Fediverse