Dense graphs are antimagic

N. Alon, G. Kaplan, A. Lev, Y. Roditty, R. Yuster

Research output: Contribution to journalArticlepeer-review

89 Scopus citations

Abstract

An 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 antimagic if it has an antimagic labeling. A conjecture of Ringel (see) states that every connected graph, but K2, is antimagic. Our main result validates this conjecture for graphs having minimum degree ω(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 K2) and graphs with maximum degree at least n - 2 are antimagic.

Original languageEnglish (US)
Pages (from-to)297-309
Number of pages13
JournalJournal of Graph Theory
Volume47
Issue number4
DOIs
StatePublished - Dec 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Antimagic
  • Labeling

Fingerprint

Dive into the research topics of 'Dense graphs are antimagic'. Together they form a unique fingerprint.

Cite this