[Nauty] What are the differences between using and not using the -t option in labelg for canonical graph labeling?

[Gordon Royle]

What you say below is not correct – SageMath does not use Traces.

In fact, Sage has two algorithms, its own algorithm and one called Bliss – you can access these with

g.canonical_label(algorithm=’sage’)
g.canonical_label(algorithm=’bliss’)

and labelg also has two algorithms - namely the original nauty and Traces - that you can access with

labelg
labelg -t

If you start with, say, the Petersen graph, then all four algorithms give four different canonically labelled graphs.


In Sage, if you run

pet = graphs.PetersenGraph()
print(pet.canonical_label(algorithm='sage').graph6_string())
print(pet.canonical_label(algorithm='bliss').graph6_string())

then the output is

I at OZCMgs?
I[O[Q_c?w


If you create a file containing the Petersen graph and use labelg then you get

>A labelg pet
IsP at OkWHG
>A labelg -t pet
I[OYcOc?w


Mathematica supplies two canonical labelling algorithms, either nauty or Bliss.


The moral of the story is that the canonical labelling is defined by the algorithm, and so you have to use the same algorithm (with the same settings) to be able to compare graphs in this way.

Gordon




From: Nauty <nauty-bounces at anu.edu.au> on behalf of lczhangmath via Nauty <nauty at anu.edu.au>
Date: Sunday, 21 July 2024 at 4:32 PM
To: Brendan McKay <Brendan.McKay at anu.edu.au>
Cc: nauty <nauty at anu.edu.au>
Subject: Re: [Nauty] What are the differences between using and not using the -t option in labelg for canonical graph labeling?
Dear Brendan,

Thank you! I see now. I saw many software, like sage/Mathematica, function concerning canonical labeling all use traces(-t). So I thought canonical  labeling is always unique.

Thank you again!

Best wishes,
Licheng.

---- Replied Message ----
| From | Brendan McKay via Nauty<nauty at anu.edu.au> |
| Date | 07/21/2024 22:10 |
| To | nauty<nauty at anu.edu.au> |
| Subject | Re: [Nauty] What are the differences between using and not using the -t option in labelg for canonical graph labeling? |
labelg always makes a canonical labelling, but what "canonical" means
depends on the options.
   -t, -S, -f, -i, -I, -K all change the meaning.

In order to compare some family of graphs, you have to use the same
options for all of them.

Brendan.


On 21/7/2024 11:30 pm, lczhangmath via Nauty wrote:
> Hello, everyone,
>
>
> I noticed the option -t in labelg. I would like to ask, if I don't use the -t option, will the obtained labels still be canonical? In other words, if I want to get the canonical labeling of a graph, do I have to use the -t option? I noticed that when I don't use the -t option for canonical graph labeling, the graph's labels also change. So, what is labelg doing at this time? Do the obtained labels have some special meaning?
>
>
>   echo 'E{EG' |showg
>
>
>
>
> Graph 1, order 6.
>    0 : 1 2 3 5;
>    1 : 0 2;
>    2 : 0 1;
>    3 : 0 4;
>    4 : 3 5;
>    5 : 0 4;
>
>
>
>
> echo 'E{EG' |labelg |showg
>
>
> Graph 1, order 6.
>    0 : 4 5;
>    1 : 4 5;
>    2 : 3 5;
>    3 : 2 5;
>    4 : 0 1;
>    5 : 0 1 2 3;
>
>
>
>
> Use  labelg  -t:
> echo 'E{EG' |labelg  -t|showg
>
>
> Graph 1, order 6.
>    0 : 3 4;
>    1 : 2 5;
>    2 : 1 5;
>    3 : 0 5;
>    4 : 0 5;
>    5 : 1 2 3 4;
>
>
> Best wishes,
> Licheng
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> https://mailman.anu.edu.au/mailman/listinfo/nauty<https://mailman.anu.edu.au/mailman/listinfo/nauty>

_______________________________________________
Nauty mailing list
Nauty at anu.edu.au
https://mailman.anu.edu.au/mailman/listinfo/nauty<https://mailman.anu.edu.au/mailman/listinfo/nauty>
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au
https://mailman.anu.edu.au/mailman/listinfo/nauty<https://mailman.anu.edu.au/mailman/listinfo/nauty>