{
  "id": "1506.05780",
  "version": "v1",
  "published": "2015-06-18T19:30:35.000Z",
  "updated": "2015-06-18T19:30:35.000Z",
  "title": "Cayley graphs of diameter two from difference sets",
  "authors": [
    "Alexander Pott",
    "Yue Zhou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $C(d,k)$ and $AC(d,k)$ be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree $d$ and diameter $k$. When $k=2$, it is well-known that $C(d,2)\\le d^2+1$ with equality if and only if the graph is a Moore graph. In the abelian case, we have $AC(d,2)\\le \\frac{d^2}{2}+d+1$. The best currently lower bound on $AC(d,2)$ is $\\frac{3}{8}d^2-1.45 d^{1.525}$ for all sufficiently large $d$. In this paper, we consider the construction of large graphs of diameter $2$ using generalized difference sets. We show that $AC(d,2)\\ge \\frac{25}{64}d^2-2.1 d^{1.525}$ for sufficiently large $d$ and $AC(d,2) \\ge \\frac{4}{9}d^2$ if $d=3q$, $q=2^m$ and $m$ is odd.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-06-18T19:30:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cayley graph",
      "sufficiently large",
      "best currently lower bound",
      "abelian group",
      "largest order"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150605780P"
    }
  }
}