[Nauty] Canonical forms of weighted k-cubes

Jernej Azarija jernej.azarija at gmail.com
Sun Apr 14 18:42:08 AEST 2019


I am wondering if the following problem can easily be solved by using nauty.

For a fixed k, I am given a list of 2^k tuples (a_0,..., a_{2^k-1})
representing weights of the k-cube Q_k where a_i is the weight of the
vertex i of Q_k (we treat i as represented in binary form).

We say that two tuples are isomorphic if there is an isomorphism between
the respective weighted Q_k cubes. For example (10,12) and (12,10) are
isomorphic and so are (9, 15, 18, 18, 26, 9, 9, 15) and (26, 9, 9, 15, 9,
15, 18, 18). Both are not isomorphic to, (9, 18, 26, 9, 18, 15, 9, 15)

I would like to compute canonical forms of such tuples, so that isomorphic
tuples are assigned to the same tuple. While easy to solve if the tuples
are all distinct (take the permutation mapping the vertex with least weight
to 0 and permute the vertices in descending order) I don't see a direct way
to compute canonical labelings for the case of non-distinct labels.

As I'd like to minimize the code/bugs required for me to solve this I
wonder:  is there a clever way to model this problem directly with nauty?



More information about the Nauty mailing list