1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What is a certificate? $\endgroup$
    – Pål GD
    Apr 2 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
    Apr 2 at 20:00

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ OK I'm starting to understand. Thank you. $\endgroup$
    – IsoCurious
    Apr 2 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.