Dense graphs are antimagic

Abstract

Abstract 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