Canonical Labelling

The graph canonical labelling problem is to find a function

canon : G_V → G_V, s.t.

canon(G) is isomorphic to G, and

canon(G^γ) = canon(G),   ∀ γ ∈ S_n,

where the Vertex set V = {1, ..., n}, S_n is the group of all permutations over V, G_V is the set of all graphs over V, and G ∈ G_V.

Note, graphs G and G' are isomorphic iff canon(G) = canon(G').

 

One approach is to seek a labelling of G that gives the largest possible adjacency matrix, read as a binary number in some order, for example,

1 3 6 ... 2 4 8 ... 5 7 9 ... ... ... ... ...

If self-loops are not allowed, the diagonal can be ignored. If the graph is undirected, only the right-upper (or left-lower) triangle need be considered.

(It may be convenient to make V = {0, ..., n-1} in programs.)

Sources

Search for [canonical labelling maths graph] in the [bib].