Non-Singular graphs with a Singular Deck

The nn-vertex graph G(=Γ(G)) with a non-singular real symmetric adjacency matrix G, having a zero diagonal and singular (n−1)×(n−1)(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 GG 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.