淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1807201110365400
中文論文名稱 圖的整數幻譜
英文論文名稱 The Integer-Magic Spectrum of Graphs
校院名稱 淡江大學
系所名稱(中) 數學學系博士班
系所名稱(英) Department of Mathematics
學年度 99
學期 2
出版年 100
研究生中文姓名 莊枏樺
研究生英文姓名 Nan-Hua Jhuang
學號 893150010
學位類別 博士
語文別 英文
口試日期 2011-06-20
論文頁數 68頁
口試委員 指導教授-高金美
委員-傅恆霖
委員-黃國卿
委員-陳伯亮
委員-黃文中
委員-周兆智
中文關鍵字 整數幻譜  太陽圖  扇圖  輪圖  圖的結合 
英文關鍵字 integer-magic spectrum  null set  sun graph  graph join 
學科別分類
中文摘要 若 G=(V,E) 為一個無重邊之連通圖, A 為一個以 0 為加法單位元之交換群, 一個將圖上的所有邊映射到A{0} 的函數 f 即為一個邊的標號
(Labeling)。任意一組這樣的標號對應產生了另一個定義為 的
函數。若存在一個邊的標號 f 使得函數對應的都是A 中的同一個數, 則
我們稱此函數 f 為一個 A-magic 的邊標號 ,而所對應的常數則稱為
A-magic 值, 同時 G 也被稱為一個 A-magic 圖。令 Z 代表所有的整數, Zk
代表 0 到 k-1 之間的所有整數。如果 A = Zk, 則 G 為Zk -magic,並簡稱為
k-magic。在 k=1 時,Z1–magic 指的就是Z–magic。圖 G 的整數幻譜
(integer-magic spectrum) 為收集所有使得圖 G 為 Zk–magic 的整數k 所成的
集合, 以IM(G)代表之。

令 Cn 為一個n 迴圈, 在此迴圈的每條邊上附加一條路徑便產生了所謂的太
陽圖Cn(t1, t2, …, tn) (在Cn 中的第i 條邊對應附加的路徑長度為ti) 。
在第 3 章中我們得到太陽圖Cn(t1, t2, …, tn)的整數幻譜。


假設 G 和H 為點與邊都相異的兩個圖, G 和H 的結合,G + H,為一個
點集合為V(G)∪V(H),邊集合為E(G)∪E(H) ∪{uv|u in V(G), v in V(H)的圖。一個扇圖 Fn 為一個由一條路徑 Pn 和一個孤點 c 作結合所產生的圖,此時
c 稱為扇圖的軸心; 一個輪圖 Wn 為一個由一個迴圈 Cn 和一個孤點 c 作
結合所產生的圖, 此時 c 稱為輪圖的軸心。一個廣義扇圖 Fm,n 為一條路徑
Pn 和 m 個孤點作結合所產生的圖,此時 m 個孤點稱為此廣義扇圖的軸心;
一個廣義輪圖 Wm,n 為一條迴圈 Cn 和 m 個孤點作結合所產生的圖,此時m
個孤點稱為此廣義輪圖的軸心。在第4 章以及第5 章中我們分別得到廣義扇圖Fm,n 以及廣義輪圖 Wm,n 的整數幻譜。 在第 6 章中我們分別討論兩個路徑的
結合、兩個迴圈的結合、以及一條路徑與一迴圈的結合的圖,並得到這些圖的
整數幻譜。
一個樹圖為一個不含迴圈之連通圖。 一個蜘蛛圖為一個樹圖且只含有一
個點的度數超過 2。在第 7 章中我們探討了兩個蜘蛛圖作結合所產生的圖的
整數幻譜, 並且對於兩個樹圖作結合所產生的圖的整數幻譜有了一些猜測。
英文摘要 Let G = (V,E) be a connected simple graph and A a nontrivial Abelian group
with identity 0. A mapping f : E → A{0} is called an edge labeling of G. Any such
labeling f induces a mapping f +:V → A, defined by f +(v) = for each v in V. If
there exists an edge labeling f whose induced mapping f + on V is a constant map, then f is
an A-magic labeling, G is an A-magic graph, and the corresponding constant is called an
A-magic value. Let Z be the set of all integers and Zk = {0,1,2,…,k−1}. If A = Zk, then G
is called Zk-magic or k-magic in short. The set of all k for which G is k-magic is called the
integer-magic spectrum of G and denoted by IM(G). For convenience, Z1- magic graphs
are considered to be Z-magic.
Let Cn = (v1, v2, …, vn) be an n-cycle and for each i, 1 ≤ i ≤ n, Hi = [ui,1, ui,2, … , ui,ti+1]
be a path of length ti ≥ 2. For each i = 1, 2, …, n, attach Hi to the cycle Cn by identifying vi
and vi+1 with ui,1 and ui,ti+1 respectively, we obtain a sun graph with index n and parameters
t1, t2, …, tn, denoted by Cn(t1, t2, …, tn). In Chapter 3, we obtain the integer-magic spectra
of Cn(t1, t2, …, tn) .
A fan Fn, n ≥ 2 is a graph obtained by joining all vertices of the path Pn to a further
vertex c called the center of Fn and a wheel Wn, n ≥ 3 is a graph obtained by joining all
vertices of the cycle Cn to a further vertex c called the center of Wn. Let m and n be
integers and m ≥1 and n ≥2. A generalized fan graph Fm,n is a graph obtained by joining all vertices of the path Pn to m centers. Let m and n be integers and m ≥1 and n ≥3. A
generalized wheel graph Wm,n is a graph obtained by joining all vertices of the cycle Cn to
m centers. In Chapter 4 and Chapter 5 we determine the integer-magic spectra of
generalized fan and wheel graphs .
Let G and H be two vertex-disjoint graphs. The join of G and H, denoted by G + H,
is a graph such that the vertex set V (G + H) = V (G) ∪V (H) and the edge set E(G + H) =
E(G)∪E(H)∪{uv | u in V (G) and v in V (H)}. In Chapter 6, we determine the integermagic
spectra of the join of two paths, the join of two cycles, and the join of a path and a
cycle .
A tree T is a connected graph with no cycle. A spider is a tree with at most one
vertex of degree more than two, called the center of spider (if no vertex of degree more
than two, then any vertex can be the center). In Chapter 7 we discuss the null set of the
join of two spiders. From the result of the null set of the join of two spiders, we give a
conjecture about the null set of the join of two trees.
論文目次 Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..1
2 Definitions and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Sun Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Generalized Fan Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Generalized Wheel Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6 The Join of Paths and Cycles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.1 The join of two paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.2 The join of two cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.3 The join of a path and a cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
7 The Join of two Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
7.1 The join of two spiders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
7.2 The join of two Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

List of Figures
2.1 The graph of G and G|u,v . . . . . . . . . . . . . . 8
3.1 The sun graph C5(3, 2, 4, 2, 5) . . . . . . . . . . 9
3.2 Labeling of the sun graph C3(2, 3, 3) . . . . . . . 10
3.3 C5(3, 2, 4, 2, 5) shrunk to C5(3, 2, 2, 2, 3) . . . .14
3.4 Labeling of C3(2, 3, 3) . . . . . . . . . . . . . . .16
3.5 The labeling of C4(2, 3, 3, 3) . . . . . . . . . . . 16
3.6 Partial label of Cn(t1, t2, · · · , tn) . . . . . . .18
3.7 Partial label of Cn(t1, t2, · · · , tn) . . . . . . .19
3.8 Partial label of Cn(t1, t2, · · · , tn) . . . . . . .19
3.9 Partial label of Cn(t1, t2, · · · , tn) . . . . . . .20
3.10 Partial label of Cn(t1, t2, · · · , tn) . . . . . . 20
3.11 Partial label of Cn(t1, t2, · · · , tn) . . . . . . 21
3.12 Partial label of Cn(t1, t2, · · · , tn) . . . . . . 22
3.13 Partial label of Cn(t1, t2, · · · , tn) . . . . . . 22
3.14 Partial label of Cn(t1, t2, · · · , tn) . . . . . . 23
4.1 The graph O3 + P4 . . . . . . . . .. . . . .. . . . .25
4.2 Labeling of Fn . . . . . . . . . . . . . . . . . . . 26
4.3 h-zero-sum labelling of F5, F6, and F7 . . . . . . . 27
4.4 G||u,v and G . . . . . . . . . . . . . . . . . . . . 28
4.5 The labeling of G||u,v and G . . . . . . . . . . . . 28
4.6 The graph of F8 and F8ka1,a5 . . . . . . . . . . . . 29
4.7 The labeling of Fm,2 . . . . . . . . . .. . . . . . 32
4.8 The labeling of Fm,3 . . . . . . . . . . . . . . . . 35
4.9 h-zero-sum labeling of F3,3 . . . . . . . . . . . . .36
4.10 h-zero-sum labeling of F2,4 . . . . . . . . . . . . 36
4.11 h-zero-sum labeling of F2,5 . . . . . . . . . . . . 37
4.12 3-zero-sum labeling of F3,5 . . . . . . . . . . . . 37
4.13 3-magic labeling of F7 and F9 . . . . . . . . . . . 39
4.14 The labeling of G||u,v and G . . . . . . . . . . . 39
4.15 3-magic labeling in F6 . . . . . . . . . . . . . . 40
4.16 3-magic labeling of F2,3, F3,3 and F4,3 . . . . . . 40
4.17 Extended of labeling from Fm,n to Fm+3,n . . . . . .40
5.1 The graph O3 + C3 . . . . . . . . . . . . . . . . . .41
5.2 Labeling of Wn . . . . . . . . . . . . . . . . . . . 42
5.3 h-zero-sum labeling of W3,W4, and W8 . . . . . . . . 43
5.4 h-zero-sum labeling of W5 for h ≥ 5 and 4-zero-sum labeling of W5 . . . . . . . . . . . . . . . . . . . . . 44
5.5 h-zero-sum labeling of W2,3 . . . . . . . . . . . . .47
5.6 h-zero-sum labeling of W3,4 . . . . . . . . . . . . .47
5.7 3-magic labeling of W4 and W5 . . . . . . . . . . . .48
6.1 The graphs G + H and G(2, xx′) + H(1, yy′) . . . . 49
6.2 h-zero-sum labeling of P2 + P2 . . . . . . . . . . . 51
6.3 h-zero-sum labeling of P2 + P3 . . . . . . . . . . . 51
6.4 h-zero-sum labeling of P3 + P3 . . . . . . . . . . . 52
6.5 h-zero-sum labeling of C3 + C3 . . . . . . . . . . . 53
6.6 h-zero-sum labeling of P2 + C4 . . . . . . . . . . . 55
6.7 h-zero-sum labeling of P3 + C3 . . . . . . . . . . . 56
6.8 3-zero-sum labeling of P3 + C4 . . . . . . . . . . . 57
7.1 A tree T . . . . . . . . . . . . . . . . . . . . . . 59
7.2 A decomposition of Sp(3, 1, 1) + P3 . . . . . . . . .60
7.3 A spider Sp(1, 1, 3, 2, 2, 1) . . . . . . . . . . . .61
7.4 Two book graphs . . . . . . . . . . . . . . . . . . 61
7.5 Edge decomposition of Sp(3, 1, 1) + Sp(1, 1) . . . . 62
7.6 Graphs of Type 1 with 1, 2, or 3 pages . . . . . . . 64
7.7 Graphs of Type 2 with 1 or 2 pages . . . . . . . . . 64
7.8 Graphs of Type 3 with 1 or 2 pages . . . . . . . . . 65
參考文獻 References
[1] C. Berge, Regularisable graphs II, Discrete Math., 23 (1978), 91–95.
[2] S. M. Lee, A. Lee, H. Sun, and I.Wen, On the integer-magic spectra of graphs,
JCMCC 42 (2002), 77–86.
[3] R.M. Low and S. M. Lee, On Group-Magic Eulerian Graphs, JCMCC, 50
(2004), 141–148.
[4] E. Salehi, Zero-Sum Magic Graphs and their Null Sets, Ars Combin., 82
(2007), 41–53.
[5] J. Sedl′aˇcek, Problem 27, in Theory of Graphs and its Applications, Proc.
Symposium Smolenice, June, (1963) 163–167.
[6] W.C. Shiu, R.M. Low, Integer-magic spectra of sun graphs, J Comb Optim,
14 (2007), 309–321.
[7] W.C. Shiu and R.M. Low, Zk-magic labelings of fans and wheels with magicvalue
zero, Australas. J. Comb., Volume 45 (2009), 309–316.
[8] R.P. Stanley, Linear Homogeneous Diophantine Equations and Magic Labelings
of Graphs, Duke Math. J. 40 (1973), 607–632.
68
[9] R.P. Stanley, Magic Labelings of Graphs, Symmetric Magic Squares, Systems
of Parameters, and Cohen-Macaulay Rings, Duke Math.J. 43 (1976), 511–531.
[10] B. M. Stewart, Magic graphs, Canadian J. Math., 18 (1966), 1031–1059.
[11] B. M. Stewart, Supermagic complete graphs, Canadian J. Math., 19 (1967),
427–438.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2011-07-25公開。
  • 同意授權瀏覽/列印電子全文服務,於2011-07-25起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信