{
  "id": "1112.5101",
  "version": "v1",
  "published": "2011-12-21T17:17:48.000Z",
  "updated": "2011-12-21T17:17:48.000Z",
  "title": "On prisms, Möbius ladders and the cycle space of dense graphs",
  "authors": [
    "Peter C. Heinig"
  ],
  "comment": "33 pages; 5 figures",
  "journal": "European Journal of Combinatorics 36 (2014), 503-520",
  "doi": "10.1016/j.ejc.2013.09.005",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a graph X, let f_0(X) denote its number of vertices, d(X) its minimum degree and Z_1(X;Z/2) its cycle space in the standard graph-theoretical sense (i.e. 1-dimensional cycle group in the sense of simplicial homology theory with Z/2-coefficients). Call a graph Hamilton-generated if and only if the set of all Hamilton circuits is a Z/2-generating system for Z_1(X;Z/2). The main purpose of this paper is to prove the following: for every s > 0 there exists n_0 such that for every graph X with f_0(X) >= n_0 vertices, (1) if d(X) >= (1/2 + s) f_0(X) and f_0(X) is odd, then X is Hamilton-generated, (2) if d(X) >= (1/2 + s) f_0(X) and f_0(X) is even, then the set of all Hamilton circuits of X generates a codimension-one subspace of Z_1(X;Z/2), and the set of all circuits of X having length either f_0(X)-1 or f_0(X) generates all of Z_1(X;Z/2), (3) if d(X) >= (1/4 + s) f_0(X) and X is square bipartite, then X is Hamilton-generated. All these degree-conditions are essentially best-possible. The implications in (1) and (2) give an asymptotic affirmative answer to a special case of an open conjecture which according to [European J. Combin. 4 (1983), no. 3, p. 246] originates with A. Bondy.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-21T17:17:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C45",
      "05C50",
      "37F20"
    ],
    "keywords": [
      "cycle space",
      "möbius ladders",
      "dense graphs",
      "hamilton circuits",
      "simplicial homology theory"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.5101H"
    }
  }
}