Dense graphs are antimagic

An antimagic labeling of graph a 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 4) states that every connected graph, but K 2 , 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 K 2 ) and graphs with maximum degree at least n  – 2 are antimagic. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 297–309, 2004