nauty binary package in Ubuntu Xenial amd64

 nauty (No AUTomorphisms, Yes?) is a set of procedures for computing
 automorphism groups of graphs and digraphs. This mathematical software
 suite is developed by Brendan McKay and Adolfo Piperno:
 http://pallini.di.uniroma1.it
 .
 nauty computes graph information in the form of a set of generators,
 the size of the group, and the orbits of the group; it can also
 produce a canonical label. The nauty suite is written in C and comes
 with a command-line interface, a collection of command-line tools,
 and an Application Programming Interface (API).
 .
 This package provides the nauty interface named dreadnaut, and a
 small collection of utilities called gtools.

Source package