Nut graphs : maximally extending cores

Abstract

A graph G is singular if there is a non-zero eigenvector v(0) in the nullspace of its adjacency matrix A. Then Av(0) = 0. The subgraph induced by the vertices corresponding to the non-zero components of v(0) is the core of G (w.r.t. v(0)). The set whose members are the remaining vertices of G is called the periphery(w.r.t. v(0)) and corresponds to the sere components of v(0). 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 greater than or equal to 7 and that among singular graphs nut graphs are characterized by their deck of spectra.