Two-graphs and NSSDs: An Algebraic Approach

Published in Discrete Applied Mathematics, 2018

Cite as: Irene Sciriha and Luke Collins. (2018). Two-graphs and NSSDs: An algebraic approach, Discrete Applied Mathematics, 266, pp. 92-102. DOI: 10.1016/j.dam.2018.05.003.

View journal webpage here.


A two-graph $(\mathscr V, \Delta)$ is a combinatorial entity consisting of a set $\mathscr V$ together with a collection $\Delta$ of unordered triples of elements of $\mathscr V$, such that there exists a graph $G$ with vertex set $\mathscr V$ in which the triples in $\Delta$ are precisely the subgraphs $K_3$ or $K_2 \mathbin{\dot\cup} K_1$ 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 $\Delta$ and therefore the switching class of $G$ is equivalent to its two-graph $(\mathscr V,\Delta)$. The graphs in a switching class have similar $(0, \pm 1)$-Seidel matrices. So the spectrum of $(\mathscr V,\Delta)$ is taken as the Seidel spectrum of a graph in the switching class. The two graphs with exactly two distinct Seidel eigenvalues $\mu_1, \mu_2$ are regular. We show how an involution $\mathbf M(\mu_1,\mu_2)$ provides a simple way to determine structural and combinatorial properties of the graphs of a regular two-graph. If $\mu_1+\mu_2=0$, the regular two-graph consists of conference graphs. We show that $\mathbf M(\mu_1,-\mu_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.

Additional Information

I gave a talk about the research presented in this paper.

Leave a Comment