臺灣博碩士論文加值系統

令G 是一個有m 個點, n 個邊的圖, 若f 是一個由V(G) 對應到{0,1,2,···,n} 的一對一函數◦ 使得每個邊uv 的值為|f(u)−f(v)|,且每個邊所產生的值都不一樣, 則我們稱f 為 G 的優美標號(Graceful labeling)◦

令f 為圖形G 的優美標號, 如果存在一個正整數λ, 使得G 的每個邊uv 都滿足f(u) ≤
λ < f(v) 或f(v) ≤ λ < f(u), 我們稱f 為G 的一個α-標號◦ 此整數λ 稱為臨界值(critical
value)◦

令r 和ℓ 為兩個正整數, ㄧ個二部圖G定義為G = A∪B, 其中點集合A={a0,a1,a2,...,aℓ−1}及點集合B={b0, b1, b2,...,bℓ−1}, 且A∩B=∅, 若滿足對於每一個i∈Zℓ, ai 與bj 皆相連若且唯若j∈{i,i+1,i+2,···,i+r−1} (mod ℓ), 則我們稱G為(r,ℓ)-皇冠圖◦

在這篇論文中, 我們將證明：若r 為奇數, 且ℓ=2r−4, 則(r,ℓ)-皇冠圖有一個α-標號◦

Let G be a graph with m vertices and n edges. A graceful labeling of G is an injection f:V(G)→{0,1,2,...,n} such that, when each edge uv is assigned the label |f(u)−f(v)|, the resulting edge labels are distinct. We call f is a graceful labeling of G.

A graceful labeling is called an α- labeling if there exists an interger λ such that for
each edge uv either f(u) ≤ λ < f(v) or f(v) ≤ λ < f(u). The integer λ is called critical
value.

Let r and ℓ be two positive integers. A bipartite graph G defined on G=A∪B
, where A∩B=∅, A={a0,a1,a2,···,aℓ−1} and B={b0,b1,b2,··· ,bℓ−1} is called an (r,ℓ)−crown, for each i∈Zℓ, ai is adjacent to bj if and only if j∈{i,i+1,i+2,···,i+r−1}(mod ℓ).

In this article, we will prove that for each odd integer r ≥ 5, an (r,ℓ)-crown has an
α-labeling, where ℓ=2r−4.

中文摘要 I
Abstract II
誌謝 III
contents IV
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . 1
1.2 The Preliminaries in Graph Theory . . . . . . . . . . . . . . . . . . . . . 1
1.3 The Preliminaries in Vertex-Labeling . . . . . . . . . . . . . . . . . . . . 4
1.4 Some Results about Vertex-Labeling . . . . . . . . . . . 4
2 The Main Result 10
3 Concluding Remark 33
References 34

List of Figures
1 G is an (5, 12)-crown. . . . . . . . . 4
2 A graceful labeling of Cn, n ≡ 0 (mod 4), is also an α-labeling. . . . . . . 5
3 A graceful labeling of Cn, n ≡ 0 or 3 (mod 4), has no α-labeling. . . . . . 5
4 Graceful labeling of K2,K3 and K4. . . . . 6
5 An α-labeling of Pn. . .. . . . . . . . . 6
6 An α-labeling of caterpillar. . . . . . . . . . . . 6
7 An α-labeling of K4,3,K4,4 and K4,5. . . . . 7
8 An α-labeling of Q3. . . . . . . . . . 7
9 An α-labeling of C6 × P5. . . . . . . . 7
10 An α-labeling of C6 × P3. . . . . . . 8
11 eG is an (5,12)-crown. . . . . . . 10
12 An α-labeling of (5,6)-crown. . . .. . 11
13 An α-labeling of (7,10)-crown. . . . . . 11
14 An α-labeling of (9,14)-crown. . . . . 12
15 A partition {H1,H2,H3,H4,H5} of C. . . .. 15
16 H1 . . . . . . 16
17 H2 . . . . . . . . . . . . . . . 16
18 H3, for i ∈[0, r−13/2] and r > 11. . . . 17
19 H4, for i ∈ [0, 2]. . . . . . . . . . . 17
20 H5, for i ∈[0, r−9/2]. . . . . 18
21 An α-labeling of (13, 22)-crown. . . . . 30
22 (11,18)-crown. . . . . . . . . . . . . 31
23 (15,26)-crown. . . . . . . . . . . 32

[1] Juraj Bos ak, Decompositions of Graphs, Dordrecht; Boston: Kluwer Academic Publishers,
1990 1st English ed.
[2] Reinhard Diestel, Graph Theory Electronic Edition, Springer-Verlag Heidelberg,
New York, 1997, 2000, 2005.
[3] S. El-Zanati and C. Vanden Eynden, Decompositions ofKm,n into Cubes, J. Combin.
Designs, 4 (1996), pp. 51-57.
[4] J. A. Gallian, A Dynamic Sarvey of Graph Labeling, E. J. of combinatorics, 15(2008),
♯DS 6.
[5] 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.
[6] Hsi-Chen Kao, On α-labeling of Prism Graphs, 中原應用數學系碩士論文, 2008.
[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] Chi-Ying Yang, On α-labelings of even-degree (r, 2r − 4)-Crowns, 中原應用數學系碩
士論文, 2009.
[17] Yan-Lan Yang, On α-labelings of odd-degree Crowns, 中原應用數學系碩士論文, 2008.
35