| Abstract: | 圖形標號顧名思義是給定圖形中的點(或)邊上一些數字,使得它滿足一些特定的條件。於1970年,Rosa首先提出了邊魔方(edge magic total)的觀念。之後於1998年由 Enomoto 提出超邊魔方(Super edge magic):假設圖形擁有p個點和q個邊,如果存在一對一函數f:V(G)U E(G) → {1,2,3....,p+q},使得對所有uv 屬於E(G),皆符合 f(uv)+f(u)+f(v)=m為一常數,則f稱為邊魔方(edge magic total)標號。如果進一步要求f:V(G) → {1,2,3ldots,p}$,則此邊魔方標號稱為超邊魔方標號。在2006年由Figueroa-Centeno提出了超邊魔方缺數(Super dege magic deficiency)的觀念:如果一圖形加上最少m個孤立點,使得此圖形成為超邊魔方圖。則我們將m值稱做此圖形的超邊魔方缺數。如果此圖形本身就是超魔方圖,則其缺數為0。如果無法靠加任何孤立點使此圖形成為超邊魔方圖,則缺數為無限。Figueroa-Centeno 對一些基本圖形計算超邊魔方缺數。而且猜測完全二部圖Km,n的超邊魔方缺數為(m-1)(n-1)。我們將完整證明這個猜測。我們也討論超邊魔方缺數與一些傳統標號之間的關係。更在提出了廣義超邊魔方缺數的觀念,同時針對討論了算數標號(Arithmetic labeling)的頂點標號的最小範圍作出了討論,並且也提出了一些結果。
A (p, q) graph is a finite simple undirected graph G with p verticesand q edges. G is called edge magic if there exists a bijection f :V (G) U E(G) → {1, 2, · · · · · · , p + q} such that f(u) + f(v) + f(uv) is constant for every edge uv ? E(G). Moreover, G is called super edge magic if f(V (G)) = {1, 2, · · · · · · , p}. We study the graphs for which it is possible to add a finite number of isolated vertices, if needed, so that the resulting graph is super edge magic. The super edge magic deficiency of a graph G is the minimum number of isolated vertices added to G so that the resulting disconnected graph to be super edge magic. On the other hand, In 1990, Acharya and Hegde have introduced the concept of strongly k-indexable graphs. A (p, q) graph G is said to be strongly k-indexable if its vertices can be assigned distinct numbers 0, 1, · · · · · · , p ? 1 so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices, form an arithmetic progression k, k + 1, · · · · · · , k + q ? 1. It is easy to see that a graph is super edge-magic if and only if it is strongly k-indexable for some k. Acharya and Hegde called the super edge magic deficiency of a graph G to be vertex dependent characteristic of G. Among others, for the complete bipartite graph Km,n we completely determine their super edge magic deficiency in this thesis. Also more general situations are obtained for various classes of graphs. |
