臺灣博碩士論文加值系統

於西元1967年,Rosa為首位使用圖形標號作為圖形分割工具的學者.從那時起,就有相當多不同的標號種類被研究出來.近來,J.A. Gallian所著論述,將標號問題的研究做全面性整理.
Rosa 首先介紹Beta標號和Alpha標號.特別是後者,對於分割一圖至循環同構子圖提供了一個重要的工具.因此,知道許多圖形具有Alpha標號是令人感興趣地.
令圖形G擁有q個邊(edges),有一對映函數(injective function)f:V(G)---> {0,1,2,..., q},是將圖形G的每一節點(vertices)從0至q加以編號,使得每對相鄰的節點uv,|f(u)-f(v)|的值皆不同(distinct),則我們稱此函數f為圖形G的一個Beta標號(Beta-labeling).一個Beta標號又稱作是一個完美標號(Graceful labeling).而Alpha標號(Alpha-labeling)為完美標號再增加一性質,即存在一整數lambda,使得對於每邊uv,滿足f(u)<= lambda<f(v)或f(v)<=lambda<f(u).
角柱體圖C_{m} X P_{2t+1}是長度為m的圈(cycle)與擁有n個節點之路徑(path)做笛卡兒乘積(cartesian product)運算所形成,其中m>=3,n>=2.節點為n的輪子圖(wheel graph)是由擁有n個節點之圈與圈外另一節點相連接所形成的圖,若在輪子圖外圈的每一邊各增加一節點,則我們稱此圖為齒輪圖(gear graph).兩圖形皆已被證明具有完美標號.在此篇論文中,我們證明C_{6} X P_{2t+1}以及齒輪圖皆具有Alpha標號.

Let G be a graph with q edges, we call a function f a β-labeling of G if f is an injective
function from the vertices of G to{0,1,2, . . . , q} such that all values |f(u)−f(v)| for the q pairs of adjacent vertices u and v are distinct. A β-labeling is also known as a graceful labeling. An α-labeling is a graceful labeling with additional property that there is an integer λ such that for each edge uv either f(u)<=λ<f(v) or f(v)<=λ<f(u).
A prism graph is defined as the cartesian product Cm ×Pn of a cycle of length m and a path with n vertices, where m>=3 and n>=2. A wheel graph Wn of order n + 1 which contains a cycle of order n, and for which every vertex in the cycle is connected to one other vertex. A gear graph Gn is a graph obtained from a wheel graph Wn by adding a vertex between every pair of adjacent vertices of the outer cycle. In this thesis, we first show that C6 × P2t+1 has an α-labeling for t>=1, and then we also show that each gear graph has an α-labeling.

1 Introduction .............................................................2
1.1Motivation ............................................................2
1.2 The Preliminaries in Graph Theory ....................................2
1.3 Graph decompositions and vertex labelings ............................3
1.4 Some Result about α-labeling .........................................4
2 The main result about prism graph ........................................7
3 The main result about gear graph ........................................14
4 Concluding Remark .......................................................20
Reference .................................................................20

[1] Douglas S. Jungreis and Michael Reid, Labeling Grids, Ars combinatoria, 34 (1992), pp. 167-182.
[2] S. El-Zanati and C. Eynden, Decompositions of Km,n into Cubes, J. Combin. Designs,4(1996), pp. 51-57.
[3] G. Chartrand, Introudction to graph theory, McGraw-Hill Higher Education, c2005 1st ed.
[4] Jen-Hsin Huang and Srecen S. Skiena, Gracefulling Labeling Prisms, Ars Combin., 38(1994), pp. 225-242.
[5] Joseph A. Gallian, A Dynamic Survey of Graph Labeling, The Electronic Journal of Combinatorics, 5(2005).
[6] K. J. Ma and C. J. Fing, On the gracefulness of gear graphs, Math. Practice Theory, (1984), pp. 72-73.
[7] M. Maheo, Strongly Graceful Graphs, Discrete Math., 29(1980), pp. 39-46.
[8] A. Rosa, On Certain Valuations of The Vertices of a Graph, in: Th´eoriedes graphes-Theory of Graphs(Journ´ees int.d’´etude, Rome, 1996), ed. Rosenstiehl, P., Dunod, Paris-Gordon and Breach, New York,(1967), pp. 349-355.
[9] C. L. Shiue, 圖的分割與點的標號(II), 國科會計畫結案報告, NSC 92-2115-M-033-003.
[10] C. L. Shine and H. L. Fu, α-labeling unmber of trees, submitted.