[Nauty] Canonical forms of weighted k-cubes

Jernej Azarija jernej.azarija at gmail.com
Sun Apr 14 20:07:37 AEST 2019


Yeah, this was my first impression but perhaps I missed something.

I took the graph6 string of the canonical form of the respective colored
graph + the sorted tuple as a "canonical certificate" for a tuple. Somehow
this was not reducing tuples properly, though.

Am I missing something with the above or should I take a deeper look into
the code?

Best,

Jernej

On Sun, Apr 14, 2019, 11:10 Gordon Royle <gordon.royle at uwa.edu.au> wrote:

> 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
>


More information about the Nauty mailing list