{
  "id": "1407.6329",
  "version": "v1",
  "published": "2014-07-23T18:41:52.000Z",
  "updated": "2014-07-23T18:41:52.000Z",
  "title": "Perfect codes in Doob graphs",
  "authors": [
    "Denis Krotov"
  ],
  "comment": "11pp",
  "categories": [
    "math.CO",
    "cs.IT",
    "math.IT"
  ],
  "abstract": "We study $1$-perfect codes in Doob graphs $D(m,n)$. We show that such codes that are linear over $GR(4^2)$ exist if and only if $n=(4^{g+d}-1)/3$ and $m=(4^{g+2d}-4^{g+d})/6$ for some integers $g \\ge 0$ and $d>0$. We also prove necessary conditions on $(m,n)$ for $1$-perfect codes that are linear over $Z_4$ (we call such codes additive) to exist in $D(m,n)$ graphs; for some of these parameters, we show the existence of codes. For every $m$ and $n$ satisfying $2m+n=(4^t-1)/3$ and $m \\le (4^t-5\\cdot 2^{t-1}+1)/9$, we prove the existence of $1$-perfect codes in $D(m,n)$, without the restriction to admit some group structure. Keywords: perfect codes, Doob graphs, distance regular graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-07-23T18:41:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "94B05",
      "94B25",
      "05B40"
    ],
    "keywords": [
      "perfect codes",
      "doob graphs",
      "distance regular graphs",
      "group structure",
      "necessary conditions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1407.6329K"
    }
  }
}