臺灣博碩士論文加值系統

令圖形G 是個有q 個邊(edges)的圖, 且f 是將V(G)對應到{0, 1, 2, · · · , q}的一對一函數.假設邊e的兩個端點為u 和v,則我們稱| f(u) − f(v) |為e的值.如果f 對G 的q個邊所產生的值都不一樣,則我們稱f 為β-標號.現今β-標號又常被稱為完美標號(Gracefullabeling).
令函數f 為圖形G 的一個β-標號, 若存在一個正整數λ, 此正整數λ稱為臨界值(critical value), 使得對每一個G 上的uv, 皆滿足f(u) ≤ λ < f(v) 或f(v) ≤ λ < f(u) 的條件, 則
我們稱f 為G 的α-標號.
若一個二分圖G定義在A∪B, 其中點集合A = {a0, a1, a2, · · · , aℓ-1},B = {b0, b1, b2, · · · ,
bℓ-1}, 且A ∩ B =∅.令r和ℓ為兩個正整數,如果滿足對於每一個i ∈ Zℓ, ai皆與bj相連, 若且唯若j ∈ {i, i + 1, i + 2, · · · , i + r − 1}(modℓ), 則我們稱G = (A,B)為(r, ℓ)-皇冠圖.若r為偶數, 我們則稱G為偶數度(r, ℓ)-皇冠圖.
在此篇論文中, 我們證明若r ≥ 6 , 則偶數度(r, 2r−4)-皇冠圖有一個α-標號.

Let G be a graph with q edges, and f be an injection from V (G) into {0, 1, 2, · · · , q}.
We call f is a β-labeling of G, if the values | f(u)−f(v) | for the q pairs of adjacent vertices
u and v are distinct. A β-labeling is now more commonly called a graceful labeling.
An α-labeling is a graceful labeling having the additional property that there is an
interger λ which is called a critical value so that for each edge {u, v} ∈ E (G) either
f(u) ≤ λ < f(v) or f(v) ≤ λ < f(u).
A bipartite graph G is defined on A ∪ B , which A = {a0, a1, a2, · · · , aℓ-1} , B =
{b0, b1, b2, · · · , bℓ-1}, and A∩B =∅. Let r and ℓ be two positive integers , for each i ∈ Zℓ,
ai is adjacent to bj if and only if j ∈ {i, i+1, i+2, · · · , i+r−1}(mod ℓ) then G = (A,B)
is called an (r, ℓ)-crown. An (r, ℓ)-crown is said to be even-degree if r is even.Otherwise,it is odd-degree.
In this thesis, we prove that for each even integer r ≥ 6, an even-degree (r, 2r − 4)-
crown has an α-labeling.

中文摘要 I
Abstract II
誌謝 III
contents IV
List of Figures V
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . 1
1.2 The Preliminaries in Graph Theory . . . . . . . . . . . . . . . . . . . . . 1
1.3 The Preliminaries in Vertex-Labeling . . . . . . . . . . . . . . . . . . . . 4
2 The Main Result 7
3 Concluding Remark 34
References 35

List of Figures
1 G is a(4, 12)-crown. . . . . . . . . . . . . . . . . . . . . . . . . 4
2 A graceful labeling. . . . . .. . . . . . . . . . . . . . . . . . . 4
3 An α-labeling of K4,5 with the critical value λ = 4. . . . . . . . 5
4 An α-labeling of P3,P4,P5. . . . . . . . . . . . . . . . . . . . . . 5
5 An α-labeling of caterpillar(λ = 7). . . . . . . . . . . . . . . . . 6
6 Graceful labeling of K2,K3 and K4. . . . . . . . . . . . . . . . 6
7 An α-labeling of Q3(λ = 3). . . . . . . . . . . . . . . . . . . 6
8 ~G(~G is a (6, 8) − crown). . . . .. . . . . . . 8
9 An α-labeling of (6, 8)-crown. . . . . . . . . . . . . . . . . . 9
10 An α-labeling of (8, 12)-crown. . . . . . . . . . . . . 9
11 An α-labeling of (10, 16)-crown. . . . . . . . . . . . . . .. . . 9
12 ~G (if r ≥ 12). . . . . . . . . . . . . . . . . . . . . . . . . 10
13 f (di). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
14 ~G. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
15 f [c2r-8]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
16 f [c1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
17 f [c2r-5]. . . . . . . . . . . . . . . . . . . . . . . . . . . 19
18 f [c2r-7]. . . . . . . . . . .. . . . . . . . . . . . . . . 20
19 f [H1]. . . . . . . . . . . . . . . . . . . . . . . . . . 21
20 f [H2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
21 f [H3] . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
22 f [H4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
23 f [H5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
24 f [H6]. . . . . . . . . . . . . . . . . . . . . . . . 29
25 An α-labeling of (12, 20)-crown. . . . . . . . . . . . . 31
26 An α-labeling of (14, 24)-crown. . . . . . . . . . . . .. . . . 32
27 An α-labeling of (16, 28)-crown. . . . . . . . . . . . . . . 33

[1] Juraj Bos ak, Decompositions of Graphs, Dordrecht; Boston: Kluwer Academic Publishers,
1990 1st English ed.
[2] S. El-Zanati and C. Vanden Eynden, Decompositions ofKm,n into Cubes, J. Combin.
Designs, 4 (1996), pp. 51-57.
[3] J. A. Gallian, A Dynamic Sarvey of Graph Labeling, E. J. of combinatorics, 15(2008),
♯DS 6.
[4] S. W. Golomb, How to Number a Graph, in Graph Theory and Computin, (Proc.
Conference Univ. West Indies, Kingston, 1969),ed. R. C. Read, Academic Press,
New York—London, 1972, pp. 23-37.
[5] Hsi-Chen Kao, On α-labeling of Prism Graphs, 中原應用數學系碩士論文, 2008.
[6] Ai-Lien Lee,On α-labelings of odd-degree (r, 2r − 4)−crowns, 中原應用數學系碩士論
文, 2009.
[7] Chen-Chen Lee, On α-labelings of even-degree Crowns, 中原應用數學系碩士論文,
2008.
[8] Pei-Shan Lee, On α-labeling of Prism Graphs and Gear Graphs, 中原應用數學系碩士
論文, 2006.
[9] Yin-Chin Lin, On α-labeling of Crowns, 中原應用數學系碩士論文, 2005.
[10] M. Maheo, Strongly Graceful Graphs, Discrete Math., 29(1980), pp. 39-46.
[11] A. Rosa, On Certain Valuations of The Vertices of a Graph, in: The’orie des graphes-
Theory of Graphs (Journ ees int. d’ etude, Rome, 1966), ed. Rosenstiehl, P., Dunod,
Paris-Gordon and Breach, New York, 1967, pp. 349-355.
[12] Chin-Lin Shiue, 圖的分割與點的標號(II), 國科會計畫結案報告, NSC 92-2115-M-033-
003.
[13] Chin-Lin Shiue and Hung-Lin Fu, α-labeling Number of Trees, Discrete Math., 306
(2006), pp. 3290-3296.
[14] H. S. Snevily, New Families of Graph That Have α-labelings, Discrete Math., 170
(1997), pp. 185-194.
[15] D. B. West, Introduction to Graph Theory 2nd, Prentice-Hall, New Jersey, 2001.
[16] Yan-Lan Yang, On α-labelings of odd-degree Crowns, 中原應用數學系碩士論文, 2008.