### Abstract

Original language | English |
---|---|

Pages (from-to) | 188-202 |

Journal | Journal of Combinatorial Designs |

Volume | 27 |

Issue number | 3 |

DOIs | |

Publication status | Published - Mar 2019 |

### Fingerprint

### Keywords

- Deza graph
- divisible design graph
- dual Seidel switching
- involution
- strongly regular graph

### Cite this

*Journal of Combinatorial Designs*,

*27*(3), 188-202. https://doi.org/10.1002/jcd.21644

}

*Journal of Combinatorial Designs*, vol. 27, no. 3, pp. 188-202. https://doi.org/10.1002/jcd.21644

**Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$.** / Goryainov, Sergey; Haemers, Willem H.; Kabanov, Vladislav V.; Shalaginov, Leonid.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$

AU - Goryainov, Sergey

AU - Haemers, Willem H.

AU - Kabanov, Vladislav V.

AU - Shalaginov, Leonid

PY - 2019/3

Y1 - 2019/3

N2 - A Deza graph with parameters $(n,k,b,a)$ is a $k$-regular graph with $n$ vertices in which any two vertices have $a$ or $b$ ($a\leq b$) common neighbours. A Deza graph is strictly Deza if it has diameter $2$, and is not strongly regular. In an earlier paper, the two last authors et el. characterized the strictly Deza graphs with $b=k-1$ and $\beta > 1$, where $\beta$ is the number of vertices with $b$ common neighbours with a given vertex. Here we deal with the case $\beta=1$, thus we complete the characterization of strictly Deza graphs with $b=k-1$. It follows that all Deza graphs with $b=k-1$ and $\beta=1$ can be made from special strongly regular graphs, and we present several examples of such strongly regular graphs. A divisible design graph is a special Deza graph, and a Deza graph with $\beta=1$ is a divisible design graph. The present characterization reveals an error in a paper on divisible design graphs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata.

AB - A Deza graph with parameters $(n,k,b,a)$ is a $k$-regular graph with $n$ vertices in which any two vertices have $a$ or $b$ ($a\leq b$) common neighbours. A Deza graph is strictly Deza if it has diameter $2$, and is not strongly regular. In an earlier paper, the two last authors et el. characterized the strictly Deza graphs with $b=k-1$ and $\beta > 1$, where $\beta$ is the number of vertices with $b$ common neighbours with a given vertex. Here we deal with the case $\beta=1$, thus we complete the characterization of strictly Deza graphs with $b=k-1$. It follows that all Deza graphs with $b=k-1$ and $\beta=1$ can be made from special strongly regular graphs, and we present several examples of such strongly regular graphs. A divisible design graph is a special Deza graph, and a Deza graph with $\beta=1$ is a divisible design graph. The present characterization reveals an error in a paper on divisible design graphs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata.

KW - Deza graph

KW - divisible design graph

KW - dual Seidel switching

KW - involution

KW - strongly regular graph

U2 - 10.1002/jcd.21644

DO - 10.1002/jcd.21644

M3 - Article

VL - 27

SP - 188

EP - 202

JO - Journal of Combinatorial Designs

JF - Journal of Combinatorial Designs

SN - 1063-8539

IS - 3

ER -