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

Sergey Goryainov, Willem H. Haemers, Vladislav V. Kabanov, Leonid Shalaginov

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)188-202
JournalJournal of Combinatorial Designs
Volume27
Issue number3
DOIs
Publication statusPublished - Mar 2019

Fingerprint

Graph Design
Graph in graph theory
Divisible
Strongly Regular Graph
Strictly
Regular Graph
Vertex of a graph

Keywords

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

Cite this

Goryainov, Sergey ; Haemers, Willem H. ; Kabanov, Vladislav V. ; Shalaginov, Leonid. / Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$. In: Journal of Combinatorial Designs. 2019 ; Vol. 27, No. 3. pp. 188-202.
@article{23cc8e6e3bfe47ac9e5bfd0dc002aa1f,
title = "Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$",
abstract = "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.",
keywords = "Deza graph, divisible design graph, dual Seidel switching, involution, strongly regular graph",
author = "Sergey Goryainov and Haemers, {Willem H.} and Kabanov, {Vladislav V.} and Leonid Shalaginov",
year = "2019",
month = "3",
doi = "10.1002/jcd.21644",
language = "English",
volume = "27",
pages = "188--202",
journal = "Journal of Combinatorial Designs",
issn = "1063-8539",
publisher = "John Wiley and Sons Inc.",
number = "3",

}

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

In: Journal of Combinatorial Designs, Vol. 27, No. 3, 03.2019, p. 188-202.

Research output: Contribution to journalArticleScientificpeer-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 -