Antimagic labeling and canonical decomposition of graphs

作者：Barrus Michael D^*

来源：Information Processing Letters, 2010, 110(7): 261-263.

DOI：10.1016/j.ipl.2010.01.006

• Antimagic labeling
• Split graph
• Canonical decomposition
• Combinatorial problems

An antimagic labeling of a connected graph with in edges is an injective assignment of labels from {1,.... m} to the edges such that the sums of incident labels are distinct at distinct vertices. Hartsfield and Ringel conjectured that every connected graph other than K(2) has an antimagic labeling. We prove this for the classes of split graphs and graphs decomposable under the canonical decomposition introduced by Tyshkevich. As a consequence, we provide a sufficient condition on graph degree sequences to guarantee an antimagic labeling.

• 出版日期2010-3-1