乘積圖的反魔方標號及相關缺數問題

On Antimagic Labeling and Associated Deficiency Problems for Graph Products

吳熹皓(Si-Hao Wu)

指導教授 ： 傅恆霖 ； 王道明

國立交通大學/理學院/應用數學系暨研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00495

摘要

針對圖G是一個p個點及q個邊的有限簡單圖。圖G的反魔方
標號指的是在圖G邊上指定連續正整數1到q滿足頂點和是兩兩相異
的(全都不一樣)，其中某點的頂點和是這個點所連出去的邊之標號做加
總。更進一步，如果頂點和滿足首項為a和公差為d的等差數列，則
稱圖G是(a,d)反魔方圖。對於圖G的(a,d)反魔方缺數(或反魔方缺
數)被定義成存在最小值k滿足放寬可用標號為連續正整數1到q+k
是(a,d)反魔方(或反魔方)。在此論文中，我們主要研究針對某些乘積
圖的反魔方標號及相關缺數問題。特別地，我們討論偶正則圖和正則圖
的強乘積之反魔方標號，在最後，我們也描述了兩個圈的卡氏積(a,1)
和強乘積之反魔方缺數。

關鍵字

反魔方標號 ； 反魔方圖 ； 強乘積 ； 卡氏積

並列摘要

Let G = (V(G),E(G)) be a finite simple graph with p = |V (G)| vertices and
q = |E(G)| edges. An antimagic labeling of G is a bijection from the set of edges to
the set of integers {1,2,...,q} such that the vertex sums are pairwise distinct, where
the vertex sum at a vertex is the sum of labels of all edges incident to such vertex.
Moreover G is called (a,d)-antimagic if the vertex sums are a,a+d,...,a+(|V|-1)d
for some positive integers a and d. For the graph G, the (a,d)-antimagic deficiency
(antimagic deficiency, respectively) is defined as the minimum integer k such that
the injective edge labeling f : E(G)->{1,2,...,q+k} is (a,d)-antimagic (antimagic,
respectively). This thesis mainly studies antimagic labeling and associated antimagic
deficiency problems for certain graph products. In particular, we show the antimagicness
for strong product of any even regular graph and any regular graph. Also we
determine the (a,1)-antimagic deficiency for the Cartesian product of cycles and the (a,1)-antimagic deficiency for the strong product of cycles.

並列關鍵字

antimagic labeling ； antimagic graph ； strong product ； Cartesian product

參考文獻

Paris (1967) 349- 355.

[3] T.-M. Wang, Toroidal grids are anti-magic, Lecture Notes in Computer Science

(LNCS) 3595 (2005) 671-679.

[4] T.-M. Wang and C. Hsiao, On anti-magic labeling for graph products, Discrete

[5] Ying-Ren Chen, Two Edge Labelings in Graphs : Graph Decomposition and