實數標號的反魔幻圖形

Abstract

設G是一個圖，且A是複數的子集，其中|A|=|E(G)|，且E(G)為圖G的邊所成集合。標號在集合A裡頭的邊標記，是從E(G)映射到A的函數。設B是複數的子集，且|B|≥|E(G)|。若對於集合B 的每個子集A，滿足|A| = |E(G)|，而且標號在A 裡頭的邊標記，使得不同頂點它們連接的邊標記之總和是不同的，則圖G被稱為B-反魔幻。一般文獻中，若G是{1, 2, ..., |E(G)|}-反魔幻，則稱圖G是反魔幻的。反魔幻圖的概念是由Hartsfield and Ringel [11]在1990 年提出的。他們猜測至少有兩條邊的連通圖都是反魔幻的。這個猜想還沒有完全解決。許多研究人員在反魔圖領域做出了一些努力。\n設R表所有實數所成集合，且C表所有複數所成集合。我們將反魔圖的定義延伸推廣至R-反魔幻圖。在第二章，我們證明了每個R-反魔幻圖都是C-反魔幻。我們也證明了若圖G為正則圖，則R+-反魔幻圖就是R-反魔幻。另外，我們也發現了有一類正則圖是R-反魔幻。\n在第三章中，我們證明了環及點數大於等於3的完全圖是R-反魔幻。假設圖G 是環或點數大於3的完全圖，我們可以依照每個頂點邊標記總和的大小，將點以u1, u2, ..., un排序，無關乎標號的選取，這樣的性質我們就稱為均勻R-反魔幻。明顯地，每個均勻R-反魔幻, 都是R-反魔幻。我們也證明了G1□G2□...□Gn (n ≥ 2)是均勻R-反魔幻，其中每個Gi是環或點數大於等於3 的完全圖。\n在第四章，我們證明了輪子，爪子及點數大於等於6的路徑是R-反魔幻。最後，我們在第五章作研究結果總結及討論，並提出未來研究方向。

Let G be a finite graph, and A ⊆ C. An edge labeling of graph G with labels in A is an injection from E(G) to A, where E(G) is the edge set of G, and A is a subset of C. Suppose that B is a set of complex numbers with |B| ≥ |E(G)|. If for every A ⊆ B with |A| = |E(G)|, there is an edge labeling of G with labels in A such that the sums of the labels assigned to edges incident to distinct vertices are different, then G is said to be B-antimagic. A graph G is an antimagic graph in the literature, if G is {1, 2, ..., |E(G)|}-antimagic.\nThe concept of antimagic graphs was introduced by Hartsfield and Ringel [11] in 1990. They conjectured that every connected graph with at least two edges was antimagic. The conjecture has not been completely solved yet.\nWe propose the concept of R-antimagic graphs in this thesis. In Chapter 2, we prove that every R-antimagic graph is C-antimagic. We also show that every R+-antimagic graph is also R-antimagic if the graph is regular. Additionally, we discover a special class of regular graphs that are R-antimagic (see Theorem 2.3.5). One of the graphs in this class is the Peterson graph.\nIn Chapter 3, we show that cycles and complete graphs of order ≥ 3 are R-antimagic. Assume that G is a complete graph or a cycle with V (G)={u1, u2, ..., un} (n ≥ 3). We have found that all the vertices of G can be listed as u1, u2, ..., un such that for every A ⊆ R with |A|=|E(G)|, there is an edge labeling f of G with labels in A such that f +(u1) < f +(u2) < ... < f +(un). The property we call uniformly R-antimagic property which is independent of the choice of the subset A of R. Clearly, every uniformly R-antimagic is R-antimagic. We prove that Cartesian products G1□G2□...□Gn (n ≥ 2) are uniformly R-antimagic, where each Gi is a complete graph of order ≥ 2 or a cycle.\nIn Chapter 4, we prove that wheels, paws, and paths of order ≥ 6 are R-antimagic. Finally, we summarize the findings and recommend future research in Chapter 5.