Hello
I’m wanting to find out what the definition of canonical graph labelling is for the canonicalgraph function in mathematica. Any ideas where I can get that information? All I can see in the description is that it puts the graph in a canonical form, but no indication on what that form is e.g. Maximising or minimising sequences from the adjacency matrix etc.
Cheers
Graph canonization is a NP-hard computational problem. A discussion of canonical graphs is given, for example, in
For the intended application, it does not matter. What is important is that g1 and g2 are isomorphic if and only if CanonicalGraph[g1] === CanonicalGraph[g2].
There are many different ways to define (and compute) a canonical form with this property. All of them are complicated. For example, the Bliss library (which you can access in Mathematica through IGraph/M) provides multiple such forms.