{
  "id": "1306.1763",
  "version": "v3",
  "published": "2013-06-07T16:19:31.000Z",
  "updated": "2013-10-04T00:28:06.000Z",
  "title": "Bipartite graphs are weak antimagic",
  "authors": [
    "Matthias Beck",
    "Michael Jackanich"
  ],
  "comment": "This paper has been withdrawn due to a flaw in the proof of the main result",
  "categories": [
    "math.CO"
  ],
  "abstract": "The \\emph{Antimagic Graph Conjecture} asserts that every connected graph $G = (V, E)$ except $K_2$ admits an edge labeling such that each label $1, 2, ..., |E|$ is used exactly once and the sums of the labels on all edges incident with a given node are distinct. We study an associated counting function (replacing the upper bound on the possible labels by a variable) and prove that a variant of this counting function, when we do not require the labels to be distinct, is a polynomial if $G$ is bipartite. As a consequence, we show that every connected bipartite graph $G = (V, E)$ except $K_2$ admits a \\emph{weakly} antimagic labeling, that is, each edge label is among $1, 2, ..., |E|$ (repetition allowed) and the sums of the labels on all edges incident with a given node are distinct. We also present a natural extension of these results to directed and bidirected graphs; this extension gives rise to a (bi-)directed version of the Antimagic Graph Conjecture, which might be of independent interest.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-10-04T00:28:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C78",
      "05C22",
      "05C31",
      "52B20",
      "52C35"
    ],
    "keywords": [
      "bipartite graph",
      "weak antimagic",
      "edges incident",
      "edge label",
      "antimagic graph conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1306.1763B"
    }
  }
}