Premium
Dense graphs are antimagic
Author(s) -
Alon N.,
Kaplan G.,
Lev A.,
Roditty Y.,
Yuster R.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20027
Subject(s) - combinatorics , mathematics , bijection , conjecture , edge graceful labeling , vertex (graph theory) , simple graph , graph , discrete mathematics , graph labeling , line graph , graph power
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