{
  "id": "1612.06021",
  "version": "v1",
  "published": "2016-12-19T01:28:08.000Z",
  "updated": "2016-12-19T01:28:08.000Z",
  "title": "On the size of graphs without repeated cycle lengths",
  "authors": [
    "Chunhui Lai"
  ],
  "comment": "7 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1975, P. Erd\\\"os proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n)\\geq n+\\frac{107}{3}t+\\frac{7}{3}$$ for $t=1260r+169 \\,\\ (r\\geq 1)$ and $n \\geq \\frac{2119}{4}t^{2}+87978t+\\frac{15957}{4}$. Consequently, $\\lim \\inf_{n \\to \\infty} {f(n)-n \\over \\sqrt n} \\geq \\sqrt {2 + \\frac{7654}{19071}},$ which is better than the previous bounds $\\sqrt 2$ [Y. Shi, Discrete Math. 71(1988), 57-71], $\\sqrt {2.4}$ [C. Lai, Australas. J. Combin. 27(2003), 101-105]. The conjecture $\\lim_{n \\rightarrow \\infty} {f(n)-n\\over \\sqrt n}=\\sqrt {2.4}$ is not true.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-19T01:28:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C35"
    ],
    "keywords": [
      "repeated cycle lengths",
      "maximum number",
      "discrete math",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}