{
  "id": "1806.03462",
  "version": "v1",
  "published": "2018-06-09T11:41:46.000Z",
  "updated": "2018-06-09T11:41:46.000Z",
  "title": "Deza graphs with parameters $(n,k,k-1,a)$ and $β=1$",
  "authors": [
    "Sergey Goryainov",
    "Willem H. Haemers",
    "Vladislav V. Kabanov",
    "Leonid Shalaginov"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-09T11:41:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "divisible design graph",
      "parameters",
      "strictly deza graphs",
      "common neighbours",
      "special strongly regular graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}