{
  "id": "1110.1144",
  "version": "v3",
  "published": "2011-10-06T03:16:43.000Z",
  "updated": "2013-06-12T10:55:35.000Z",
  "title": "Some unsolved problems on cycles",
  "authors": [
    "Chunhui Lai",
    "Mingjing Liu"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Hajos' conjecture that every simple even graph on $n$ vertices can be decomposed into at most $(n-1)/2$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236). Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. P. Erdos raised the problem of determining $f(n)$ (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). Given a graph $H$, what is the maximum number of edges of a graph with $n$ vertices not containing $H$ as a subgraph? This number is denoted $ex(n,H)$, and is known as the Turan number. P. Erdos conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})\\geq cn^{1+1/k}$(see P. Erdos, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 97--109, Academic Press, London, 1971). This paper summarizes some results on these problems and the conjectures that relate to these. We do not think Haj\\'{o}s conjecture is true.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-06-12T10:55:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C38"
    ],
    "keywords": [
      "unsolved problems",
      "academic press",
      "graph theory",
      "conjecture",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1110.1144L"
    }
  }
}