Non-singular graphs with a singular deck

Abstract

The n-vertex graph G(= Γ (G)) with a non-singular real symmetric adjacency matrix G, having a zero diagonal and singular (n−1)×(n−1) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G−1 represent NSSDs Γ (G) and Γ (G−1), the value of the nullity of a one-, two and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in Γ (G−1). Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G-nutful graphs. We show that their minimum vertex degree is at least 4.