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

Abstract

針對圖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.