Nut graphs: Maximally extending cores

Abstract

A graph G is singular if there is a non-zero eigenvector vυ₀ in the nullspace of its adjacency matrix A. Then Aυ₀ = 0. The subgraph induced by the vertices corresponding to the non-zero components of υ₀ is the core of G (w.r.t. υ₀). The set whose members are the remaining vertices of G is called the periphery (w.r.t. υ₀) and corresponds to the zero components of υ₀. The dimension of the nullspace of A is called the nullity of G. This paper investigates nut graphs which are graphs of nullity one whose periphery is empty. It is shown that nut graphs of order n exist for each n ≥ 7 and that among singular graphs nut graphs are characterized by their deck of spectra.