In graph theory, a nut graph is a finite simple graph with at least two vertices whose adjacency matrix has a nullity equal to one and whose kernel is spanned by a vector with no zero entries. This class of graphs was introduced by Irene Sciriha and Iván Gutman in 1998. Nut graphs arise frequently in spectral graph theory and chemical graph theory.
Definition Let G {\displaystyle G} be a finite simple graph with vertex set V ( G ) = { v 1 , … , v n } {\displaystyle V(G)=\{v_{1},\ldots ,v_{n}\}} and adjacency matrix A ( G ) {\displaystyle A(G)} . The graph G {\displaystyle G} is a nut graph if n ≥ 2 {\displaystyle n\geq 2} , dim ker A ( G ) = 1 {\displaystyle \dim \ker A(G)=1} , and every nonzero vector x = [ x 1 , … , x n ] T {\displaystyle x=[x_{1},\ldots ,x_{n}]^{T}} satisfying A ( G ) x = 0 {\displaystyle A(G)x=0} has x i ≠ 0 {\displaystyle x_{i}\neq 0} for every i {\displaystyle i} . The condition dim ker A ( G ) = 1 {\displaystyle \dim \ker A(G)=1} is equivalent to saying that 0 {\displaystyle 0} is an eigenvalue of A ( G ) {\displaystyle A(G)} of multiplicity one. A vector with no zero coordinates is called a full vector. Thus, a nut graph is a graph whose adjacency matrix has a one-dimensional kernel spanned by a full vector.
Examples The smallest nut graphs have seven vertices, and the three such graphs are called the Sciriha graphs. Nut graphs exist on every order n ≥ 7 {\displaystyle n\geq 7} .
The n {\displaystyle n} -antiprism graph is a nut graph when n {\displaystyle n} is not divisible by 3 {\displaystyle 3} . The Frucht graph is a cubic polyhedral nut graph.
Properties Every nut graph is connected, non-bipartite, and without leaf vertices. Deletion of any vertex from a nut graph results in a non-singular graph.
Constructions Several graph operations are known that produce larger nut graphs from smaller ones. The coalescence of two vertex-rooted graphs ( G 1 , v 1 ) {\displaystyle (G_{1},v_{1})} and ( G 2 , v 2 ) {\displaystyle (G_{2},v_{2})} is obtained from the disjoint union of G 1 {\displaystyle G_{1}} and G 2 {\displaystyle G_{2}} by identifying v 1 {\displaystyle v_{1}} and v 2 {\displaystyle v_{2}} as a single vertex. If G 1 {\displaystyle G_{1}} and G 2 {\displaystyle G_{2}} are nut graphs, then their coalescence at arbitrary chosen vertices is again a nut graph.
Recognition and generation Nut graphs can be recognized by determining the rank or nullity of the adjacency matrix and checking whether a vector spanning the nullspace has a zero coordinate. Nutgen is a generator for nut graphs. Nutgen has been used to generate all non-isomorphic nut graphs up to 13 vertices and all chemical nut graphs up to 22 vertices. Further enumerations include nut graphs among cubic polyhedral graphs up to 34 vertices, nut graphs among fullerene graphs up to 250 vertices, and regular nut graphs for degrees up to 8. Catalogues of these nut graphs are available in the House of Graphs. The generation of nut graphs up to isomorphism can be performed by an algorithm based on the canonical construction path method.
Applications Nut graphs have been experimentally realized using coaxial cable networks.
Generalisations The notion of a nut graph has been extended to signed graphs. There are directed analogues of nut graphs. For a directed graph, the adjacency matrix need not be symmetric, so the right kernel and left kernel may differ. A digraph whose right kernel is spanned by a full vector is called dextro-nut, and a digraph whose left kernel is spanned by a full vector is called laevo-nut. A digraph satisfying both conditions is called bi-nut. A digraph is ambi-nut if it is bi-nut and its kernel and co-kernel are spanned by the same full vector.
See also Singular matrix Spectral graph theory
References
External links Weisstein, Eric W. "Nut Graph". MathWorld. Nut graphs meta-directory at the House of Graphs Nutgen: a generator for nut graphs
