[Nauty] lexicografic ordered canonical form

Joost Winne Joost.Winne at UGent.be
Wed Aug 6 18:07:02 EST 2003


Hi,

I have the following question:

Given a graph G, the canonical form produced by nauty is CANONG.
This form CANONG is not necessarely lexicograficly ordered
(lexicograficly ordered means that rows and columns are ordered
when seen as a bitstring).
There can be several ways to lexicografic order the canonical form CANONG,
since 2 lexicograficly ordered graphs can be isomorphic (if this wasn't
true we wouldn't need nauty in the first place).
Is their a way to lexicograficly order CANONG into CANONG_LEX in such a
way that it is guaranteed that CANONG_LEX is lex. smaller than all other
lex. ordered isomorphics of CANONG (G).
Otherwise put, I would like a canonical form which is also the
lexicografic smallest.

Joost





More information about the Nauty mailing list