Nut graphs




Kris Coolsaet

Patrick W. Fowler

Jan Goedgebeur

Nut graphs

Nutgen is a generator for nut graphs. A nut graph is a graph of at least 2 vertices whose adjacency matrix has nullity 1 (i.e., rank n-1 where n is the order of the graph) and for which the non-trivial kernel vector does not contain a zero.

The algorithms used in the generator are described in:

  • K. Coolsaet, P.W. Fowler and J. Goedgebeur, Generation and properties of nut graphs,
    MATCH Commun. Math. Comput. Chem., 80(2):423-444, 2018 (arXiv).

The generator can be downloaded here and a short manual can be found here. Nutgen is released under the GNU General Public License (GPL) and has been tested on Linux.

The counts of nut graphs (including downloadable lists) can be found here at the House of Graphs.

Don't hesitate to contact us at jan.goedgebeur[at] if you have any further questions or suggestions.

Last update: May 28, 2018.