# ºtÁ¿¤½§i

### ·s»D¼ÐÃD¡G¡@( 2015-10-20 )

ºtÁ¿¥DÃD¡GOn Graph Labeling of Antimagic Types with Associated Deficiency Problems

¥DÁ¿¤H¡G¤ý¹D©ú±Ð±Â (ªF®ü¤j¾Ç¼Æ¾Ç¨t)

ºtÁ¿¤é´Á¡G2015¦~11¤ë10¤é(¬P´Á¤G) ¤U¤È2:00 ¡V3:00

ºtÁ¿¦aÂI¡G(¥ú´_®Õ°Ï) ¬ì¾Ç¤@À]223«Ç

¯ù·|®É¶¡¡G·í¤Ñ¤U¤È1:30 (¬ì¾Ç¤@À]205«Ç)

ºKn¤º®e¡G

A graph labeling is usually an assignment of integers to vertices/edges(or both) of a graph which satisfies certain given conditions. The study of graph labeling can be traced back to the graceful labeling and the well known graceful tree conjecture, with motivation to solve the graph decomposition problems initiated by A. Rosa and G. Ringel et al. around 1960s. A graceful labeling for a finite simple graph G=(V,E) is an injective vertex labeling over [0,|E|] such that the induced edge weights are pairwise distinct, where the induced edge weight is the absolute difference of two end vertex labels for such edge. On the other hand, for a finite simple graph G=(V,E), an antimagic labeling is an injective edge labeling over [1,|E|] such that the induced vertex weights are pairwise distinct, where the induced vertex weight is the sum of all incident edge labels at such vertex. One may further define, as an extension, the antimagic edge deficiency number for G=(V,E) as the smallest possible integer k such that the injective edge labeling over [1,|E|+k] produces pairwise distinct induced vertex weights. Therefore the antimagic edge deficiency number of a graph is 0 if it admits an antimagic labeling. More generally, a graph labeling of antimagic type is referred to those labelings with the condition that all induced vertex/edge weights are pairwise distinct, and their associated deficiency numbers can also be similarly defined. Note that the graceful labeling can be treated as one of antimagic type, and the graceful deficiency is closely related to the optimal Golomb rulers in practical applications. In this talk, we will survey recent progress of several graph labeling of antimagic types, and introduce their associated deficiency problems.¬ÛÃöÀÉ®×¡GºtÁ¿1041110.doc

¬ÛÃöÀÉ®×¡GºtÁ¿1041110.odt