Dense graphs are antimagic
| dc.creator | Alon, N. | |
| dc.creator | Kaplan, G. | |
| dc.creator | Lev, A. | |
| dc.creator | Roditty, Y. | |
| dc.creator | Yuster, R. | |
| dc.date | 2003-04-15 | |
| dc.date.accessioned | 2026-07-07T04:56:53Z | |
| dc.date.available | 2026-07-07T04:56:53Z | |
| dc.description | 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 $Ω(\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. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/math/0304198 | |
| dc.identifier | http://arxiv.org/abs/math/0304198 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67086 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C78 | |
| dc.title | Dense graphs are antimagic | |
| dc.type | text |