Two-graphs and NSSDs : an algebraic approach

Abstract

A two-graph (V, ∆) is a combinatorial entity consisting of a set V together with a collection ∆ of unordered triples of elements of V, such that there exists a graph G with vertex set V in which the triples in ∆ are precisely the subgraphs K3 or K2∪ ̇ K1 induced in G. Switching is an equivalence relation partitioning the graphs on n vertices into switching classes. All the graphs that are switching equivalent to G yield the same ∆ and therefore the two–graph (V, ∆) is taken to consist of the graphs in the switching class of G. The graphs in a switching class have similar (0, ±1)-Seidel matrices. So the spectrum of (V, ∆) is taken as the Seidel spectrum of a graph in the switching class. The two graphs with exactly two distinct Seidel eigenvalues μ1, μ2 are regular. We show how an involution M(μ1, μ2) provides a simple

way to determine structural and combinatorial properties of the graphs of a regular two- graph. If μ1 + μ2 = 0, the regular two-graph consists of conference graphs. We show that

M(μ1, −μ1) is an NSSD (non-singular graph with a singular deck) with the special property of being a nutful graph. The rich properties of a nutful NSSD reveal new spectral properties of conference graphs.