Anti-magic labeling of trees

An anti-magic labeling of a graph G is a one-to-one correspondence between E ( G ) and { 1 , 2 , … , | E | } such that the vertex-sum (i.e., sum of the labels assigned to edges incident to a vertex) for distinct vertices are different. It was conjectured by Hartsfield and Ringel that every tree other than K 2 has an anti-magic labeling. Kaplan, Lev and Roditty proved that if a tree T has at most one degree 2 vertex, then T is anti-magic. We study trees with many degree 2 vertices, with restriction on the subgraph induced by degree 2 vertices and its complement. Denote by V 2 ( T ) the set of degree 2 vertices of T . We prove that if V 2 ( T ) and V ∖ V 2 ( T ) are both independent sets, or V 2 ( T ) induces a path and every other vertex has an odd degree, then T is anti-magic. We also correct an error in the original proof of Kaplan, Lev and Roditty.