{
  "id": "1010.5651",
  "version": "v2",
  "published": "2010-10-27T11:31:09.000Z",
  "updated": "2011-06-07T02:00:00.000Z",
  "title": "On bipartite graphs of defect at most 4",
  "authors": [
    "Ramiro Feria-Purón",
    "Guillermo Pineda-Villavicencio"
  ],
  "comment": "25 pages, 14 Postscript figures",
  "journal": "Discrete Applied Mathematics 160 (2012), 140-154",
  "doi": "10.1016/j.dam.2011.09.002",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the bipartite version of the degree/diameter problem, namely, given natural numbers {\\Delta} \\geq 2 and D \\geq 2, find the maximum number Nb({\\Delta},D) of vertices in a bipartite graph of maximum degree {\\Delta} and diameter D. In this context, the Moore bipartite bound Mb({\\Delta},D) represents an upper bound for Nb({\\Delta},D). Bipartite graphs of maximum degree {\\Delta}, diameter D and order Mb({\\Delta},D), called Moore bipartite graphs, have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree {\\Delta} \\geq 2, diameter D \\geq 2 and order Mb({\\Delta},D) - \\epsilon with small \\epsilon > 0, that is, bipartite ({\\Delta},D,-\\epsilon)-graphs. The parameter \\epsilon is called the defect. This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if {\\Delta} \\geq 3 and D \\geq 3, they may only exist for D = 3. However, when \\epsilon > 2 bipartite ({\\Delta},D,-\\epsilon)-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite $(\\Delta,d,-4)$-graphs; the complete catalogue of bipartite (3,D,-\\epsilon)-graphs with D \\geq 2 and 0 \\leq \\epsilon \\leq 4; the complete catalogue of bipartite ({\\Delta},D,-\\epsilon)-graphs with {\\Delta} \\geq 2, 5 \\leq D \\leq 187 (D /= 6) and 0 \\leq \\epsilon \\leq 4; and a non-existence proof of all bipartite ({\\Delta},D,-4)-graphs with {\\Delta} \\geq 3 and odd D \\geq 7. Finally, we conjecture that there are no bipartite graphs of defect 4 for {\\Delta} \\geq 3 and D \\geq 5, and comment on some implications of our results for upper bounds of Nb({\\Delta},D).",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-06-07T02:00:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C75"
    ],
    "keywords": [
      "maximum degree",
      "complete catalogue",
      "upper bound",
      "moore bipartite bound",
      "moore bipartite graphs"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.5651F"
    }
  }
}