Nut graph (graph theory)

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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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\ne 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. The n -antiprism graph is a nut graph when n is not divisible by 3 . The Frucht graph is a cubic polyhedral nut graph.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367045332 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.