圖的反魔術標號之探討

On Antimagic Labeling of Graphs

吳宗翰(Tsung-han Wu)

指導教授 ： 江南波

大同大學/電機資訊學院/應用數學學系所/碩士(2009年)

摘要

令G=(V,E)是一個有p個頂點及q個邊的無向圖。令f為將邊集合V對應到集合{1,2,...,q}的一對一且映成的函數。如果頂點和函數為一對一函數，則稱f為G的反魔術標號。如果圖G具有一個反魔術標號，則稱G為反魔術圖。再者，若存在正整數a、d，使得頂點和函數為一對一，且頂點和函數的值域為{a,a+d,...,a+(p-1)d}，則稱f為G的(a,d)-反魔術標號。如果G具有一個(a,d)-反魔術標號，則稱G為(a,d)-反魔術圖。
在這篇論文中，我們得到了兩個結果。第一，我們證明了所有的星圖和星圖的Cartesian乘積都是反魔術圖，其中m>=n>=3。第二，我們討論當n為奇數，n>=5，且2>=k>=(n-1)/2時，廣義的Petersen圖P(n,k)為((5n+5)/2,2)-反魔術圖這個猜測。

關鍵字

Petersen圖 ； Cartesian乘積 ； (a， d)-反魔術 ； 反魔術

並列摘要

Let G=(V,E) be an undirected graph with p vertices and q edges. Let f be a bijection function from E to {1,2,...q}. Then f is an antimagic labeling of G if the induced vertex sum is injective. If G has an antimagic labeling then we say G is antimagic. Furthermore, if there are integers a, d such that f^+ is injective, and f^+(V)={a,a+d,...,a+(p-1)d}, then f is an (a,d)-antimagic labeling of G. If G has an (a,d)-antimagic labeling then we said G is (a,d)-antimagic.
In this thesis, we obtain two results. First, we prove that all Cartesian products of star graphs with star graphs are antimagic for integers m>=n>=3. Finally, we discuss the conjecture that generalized Petersen graph P(n,k) is ((5n+5)/2,2)-antimagic for odd n, n>=5 and 2>=k>=(n-1)/2.

並列關鍵字

Petersen graph ； Cartesian product ； (a， d)-antimagic ； antimagic

參考文獻

[1] M. Baca, Consecutive-magic labeling of generalized Petersen graphs, Utilitas

Mathematica, 58(2000), pp.237-241.

[2] M. Baca and I. Hollander, On (a,d)-antimagic prisms, ARS COMBINATORIA,

[4] R. Bodendiek and G. Walther, On arithmetic antimagic edge labelings of graphs,

Mitt. Math. Ges. Hamburg, 17(1998), pp.85-99.