[Nauty-list] Hard Instances

Ramon Bejar Torres ramon at diei.udl.cat
Thu Mar 22 04:20:36 EST 2007

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.


Greg Tener wrote:
> I have three questions about hard instances for nauty (they're so few 
> and hard to find).
> I have found most of the planes at 
> http://www.uwyo.edu/moorhouse/pub/planes27/ to be difficult, some are 
> easier with using invariants such as cellfano and cellfano2.
> Hadamard equivalence of Hadamard matrices are mentioned in the new 
> users guide as well as a citing of a paper that describes a family 
> requiring exponential growth of the number of nodes.
> So, which Hadamard matrices in particular are hard? I've found some at 
> Neil Sloane's site.
> Also, are there any graphs with trivial automorphism group known to be 
> hard for nauty?
> Are there any other notable graphs which take a long time?
> University of Central Florida
> -Greg Tener-
> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list

More information about the Nauty mailing list