This package provides an interface from Macaulay2 to many of the functions provided in the software nauty by Brendan D. McKay, available at http://cs.anu.edu.au/~bdm/nauty/. The nauty package provides very efficient methods for determining whether given graphs are isomorphic, generating all graphs with particular properties, generating random graphs, and more.
Most methods can handle graphs in either the Macaulay2 Graph type as provided by the Graphs package or as Graph6 and Sparse6 strings as used by nauty. The purpose of this is that graphs stored as strings are greatly more efficient than graphs stored as instances of the class Graph. (See Comparison of Graph6 and Sparse6 formats.)
It is recommended to work with graphs represented as strings while using nauty-provided methods and then converting the graphs to instances of the class Graph for further work.
The theoretical underpinnings of nauty are in the paper: B. D. McKay, "Practical graph isomorphism," Congr. Numer. 30 (1981), 45--87.
This documentation describes version 1.4.3.1 of NautyGraphs.
The source code from which this documentation is derived is in the file NautyGraphs.m2.