We know that the Weisfeiler-Leman Algorithm will not always distinguish graphs that are not isomorphic but if two graphs are isomorphic are we guaranteed to get a certificate?
2
- $\begingroup$ What is a certificate? $\endgroup$Ainsley H.– Ainsley H.2024-04-02 19:37:50 +00:00Commented Apr 2, 2024 at 19:37
- $\begingroup$ I'm actually referring to this section from the Wikipedia article "If the certificates agree, G and H may or may not be isomorphic." I'm wondering if the graphs are isomorphic, will the certificates necessarily agree? en.wikipedia.org/wiki/Weisfeiler_Leman_graph_isomorphism_test $\endgroup$IsoCurious– IsoCurious2024-04-02 20:00:04 +00:00Commented Apr 2, 2024 at 20:00
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
1 No, because you don't actually get a mapping between graphs (at least not vertex-to-vertex mapping, but you do get a mapping between automorphism groups).
As always with the Weisfeiler Leman graph isomorphism test, you should consider three graphs, all $r$-regular graphs on $n$ vertices, two of which are isomorphic.
Every vertex of every graph will always have the same label.
- $\begingroup$ OK I'm starting to understand. Thank you. $\endgroup$IsoCurious– IsoCurious2024-04-02 21:20:30 +00:00Commented Apr 2, 2024 at 21:20