[Nauty-list] Hard Instances

[Brendan McKay]

* Ramon Bejar Torres <ramon at diei.udl.cat> [070322 05:21]:
> One particular very hard case is  the
> graph associated with a latin square, that
> is a strongly regular graph, that is
> asymmetric (it has only the trivial automorphism),
> but is very hard for Nauty to find
> the answer.
> 
> Ramon

These graphs (like many hard graphs) can be made much easier with
the help of an invariant. For Latin squares one useful invariant
is to count "cycles". A row-column cycle starts with two arbitrary
entries (r1,c1,s1), (r1,c2,s2) in the same row, then continues
(r3,c2,s1), (r3,c3,s2), ... always using the same two symbols,
eventually returning to its starting point. There are similarly
row-symbol cycles and column-symbol cycles. The lengths of these
cycles can be used to compute an invariant for the rows, columns,
and symbols of the Latin square, and from there for the vertices
of a graph deribved from the Latin square. I don't have any canned
software for this.  Another (easier but less strong) invariant
counts pairs of rows (or columns or symbols) that are related by
an even or an odd permutation.

Brendan.