Dense graphs are antimagic

Abstract

An {\em 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 {\em antimagic} if it has an antimagic labeling. A conjecture of Ringel (see \cite{HaRi}) states that every connected graph, but $K_2$, is antimagic. Our main result validates this conjecture for graphs having minimum degree $\Omega (\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.

12 pages

Cited by in corpus (17)

• Antimagic Labelings of Caterpillars
• Antimagic orientation of biregular bipartite graphs
• Cartesian Products of Regular Graphs are Antimagic
• Antimagic orientation of graphs with minimum degree at least 33
• Antimagic orientations of graphs with large maximum degree
• Antimagic orientations of disconnected even regular graphs
• Caterpillars are Antimagic
• Graphs of large linear size are antimagic
• Antimagic orientations of even regular graphs
• Lattice Grids and Prisms are Antimagic
• Antimagic orientations of graphs with given independence number
• List-antimagic labeling of vertex-weighted graphs
• Antimagic labelings of regular bipartite graphs: An application of the Marriage Theorem
• Shifted-antimagic Labelings for Graphs
• Totally Antimagic Total labeling of Ladders, Prisms and Generalised Pertersen graphs
• A note on antimagic orientations of even regular graphs
• Antimagic Orientation of Forests