부산대학교 도서관

An antimagic labelingof graph a with medges and nvertices is a bijection from the set of edges to the integers 1,…,msuch that all nvertex 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 antimagicif it has an antimagic labeling. A conjecture of Ringel (see 4) 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. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 297–309, 2004