Nut graph (graph theory)

This article is about the graph-theoretic concept. For the journalistic paragraph, see Nut graph.

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$ be a finite simple graph with vertex set $V(G)=\{v_{1},\ldots ,v_{n}\}$ and adjacency matrix $A(G)$. The graph $G$ is a nut graph if $n\geq 2$, $\dim \ker A(G)=1$, and every nonzero vector $x=[x_{1},\ldots ,x_{n}]^{T}$ satisfying $A(G)x=0$ has $x_{i}\neq 0$ for every $i$.

The condition $\dim \ker A(G)=1$ is equivalent to saying that $0$ is an eigenvalue of $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\geq 7$.

• The three smallest nut graphs
• 
  S₁
• 
  S₂
• 
  S₃

The $n$-antiprism graph is a nut graph when $n$ is not divisible by $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})$ and $(G_{2},v_{2})$ is obtained from the disjoint union of $G_{1}$ and $G_{2}$ by identifying $v_{1}$ and $v_{2}$ as a single vertex. If $G_{1}$ and $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

External links

• Weisstein, Eric W. "Nut Graph". MathWorld.
• Nut graphs meta-directory at the House of Graphs
• Nutgen: a generator for nut graphs