{
  "id": "1010.5658",
  "version": "v2",
  "published": "2010-10-27T11:55:22.000Z",
  "updated": "2011-02-26T11:51:09.000Z",
  "title": "On graphs of defect at most 2",
  "authors": [
    "Ramiro Feria-Purón",
    "Mirka Miller",
    "Guillermo Pineda-Villavicencio"
  ],
  "comment": "22 pages, 11 Postscript figures",
  "journal": "Discrete Applied Mathematics 159 (2011), no. 13, 1331-1344",
  "doi": "10.1016/j.dam.2011.04.018",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper we consider the degree/diameter problem, namely, given natural numbers {\\Delta} \\geq 2 and D \\geq 1, find the maximum number N({\\Delta},D) of vertices in a graph of maximum degree {\\Delta} and diameter D. In this context, the Moore bound M({\\Delta},D) represents an upper bound for N({\\Delta},D). Graphs of maximum degree {\\Delta}, diameter D and order M({\\Delta},D), called Moore graphs, turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree {\\Delta} \\geq 2, diameter D \\geq 1 and order M({\\Delta},D) - {\\epsilon} with small {\\epsilon} > 0, that is, ({\\Delta},D,-{\\epsilon})-graphs. The parameter {\\epsilon} is called the defect. Graphs of defect 1 exist only for {\\Delta} = 2. When {\\epsilon} > 1, ({\\Delta},D,-{\\epsilon})-graphs represent a wide unexplored area. This paper focuses on graphs of defect 2. Building on the approaches developed in [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a ({\\Delta},D,-2)-graph with {\\Delta} \\geq 4 and D \\geq 4 is 2D. Second, and most important, we prove the non-existence of ({\\Delta},D,-2)-graphs with even {\\Delta} \\geq 4 and D \\geq 4; this outcome, together with a proof on the non-existence of (4, 3,-2)-graphs (also provided in the paper), allows us to complete the catalogue of (4,D,-{\\epsilon})-graphs with D \\geq 2 and 0 \\leq {\\epsilon} \\leq 2. Such a catalogue is only the second census of ({\\Delta},D,-2)-graphs known at present, the first being the one of (3,D,-{\\epsilon})-graphs with D \\geq 2 and 0 \\leq {\\epsilon} \\leq 2 [14]. Other results of this paper include necessary conditions for the existence of ({\\Delta},D,-2)-graphs with odd {\\Delta} \\geq 5 and D \\geq 4, and the non-existence of ({\\Delta},D,-2)-graphs with odd {\\Delta} \\geq 5 and D \\geq 5 such that {\\Delta} \\equiv 0, 2 (mod D).",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-02-26T11:51:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C75"
    ],
    "keywords": [
      "maximum degree",
      "non-existence",
      "maximum number",
      "moore bound",
      "upper bound"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.5658F"
    }
  }
}