{
  "id": "1404.3948",
  "version": "v3",
  "published": "2014-04-11T14:20:25.000Z",
  "updated": "2014-08-05T14:39:02.000Z",
  "title": "The Degree-Diameter Problem for Circulant Graphs of Degree 8 and 9",
  "authors": [
    "Robert Lewis"
  ],
  "comment": "In order to avoid this paper being excessively long only an abridged version of the proof of Theorem 3 is included. The complete version is available as arXiv:1404.3949 for those interested in reading the details of all the steps",
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establish the results for degree 6 and 7 has been extended successfully to degree 8 and 9. Candidate graphs are defined as functions of the diameter for both degree 8 and degree 9. They are proven to be extremal for small diameters. They establish new lower bounds for all greater diameters, and are conjectured to be extremal. The existence of the degree 8 solution is proved for all diameters. Finally some conjectures are made about solutions for circulant graphs of higher degree.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-08-05T14:39:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "degree-diameter problem",
      "undirected circulant graphs",
      "lower bounds",
      "higher degree",
      "extremal graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.3948L"
    }
  }
}