[Nauty] Canonical forms of weighted k-cubes

[Gordon Royle]

Are these actually fundamentally different than coloured graphs?

You may need to keep the actual weights as part of the canonical form to distinguish between two graphs with the same weight partition but different actual weights.

Sent from my iPad

> On 14 Apr 2019, at 5:00 pm, Jernej Azarija <jernej.azarija at gmail.com> wrote:
> 
> Hello,
> 
> 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)
> though.
> 
> 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?
> 
> Best,
> 
> Jernej
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty