Infinite series of Deza graphs with strongly regular children

Abstract

A graph $\Gamma$ is called a Deza graph with parameters $(n, k, b, a)$ if it has exactly $n$ vertices, is $k$-regular, and for any two distinct vertices $u$ and $v$, the number of common neighbors of $u$ and $v$ is either $a$ or $b$. The graphs $\Delta_1$ and $\Delta_2$, which have the same vertex set as $\Gamma$, and in which two vertices are adjacent if they have $a$ or $b$ common neighbours, respectively, are called the children of the Deza graph. If, for a Deza graph $\Gamma$, both $\Delta_1$ and $\Delta_2$ are strongly regular graphs, then $\Gamma$ is called a strongly Deza graph. In this work, we present a construction of an infinite family of strongly Deza graphs, for which the children $\Delta_1$ and $\Delta_2$ are strongly regular graphs with the same parameters as the graphs $NO^{\varepsilon \perp}_n(5)$ and $\overline{NO^{\varepsilon \perp}_n(5)}$.