{
  "id": "math/0304198",
  "version": "v1",
  "published": "2003-04-15T15:24:36.000Z",
  "updated": "2003-04-15T15:24:36.000Z",
  "title": "Dense graphs are antimagic",
  "authors": [
    "N. Alon",
    "G. Kaplan",
    "A. Lev",
    "Y. Roditty",
    "R. Yuster"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "An {\\em antimagic labeling} of a graph with $m$ edges and $n$ vertices is a bijection from the set of edges to the integers $1,...,m$ such that all $n$ vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called {\\em antimagic} if it has an antimagic labeling. A conjecture of Ringel (see \\cite{HaRi}) states that every connected graph, but $K_2$, is antimagic. Our main result validates this conjecture for graphs having minimum degree $\\Omega(\\log n)$. The proof combines probabilistic arguments with simple tools from analytic number theory and combinatorial techniques. We also prove that complete partite graphs (but $K_2$) and graphs with maximum degree at least $n-2$ are antimagic.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2003-04-15T15:24:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C78"
    ],
    "keywords": [
      "dense graphs",
      "vertex sum",
      "main result validates",
      "analytic number theory",
      "complete partite graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math......4198A"
    }
  }
}