Dense graphs are antimagic

Details Dense graphs are antimagic Dense graphs are antimagic

2003-04-15

arxiv.org/abs/math/0304198v1

Mathematics

Combinatorics

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dense graphs are antimagic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dense graphs are antimagic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dense graphs are antimagic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-478250