角柱體圖與齒輪圖的Alpha標號

On Alpha-labelings of Prism Graphs and Gear Graphs

李佩珊(Pei-Shan Lee)

指導教授 ： 史青林

中原大學/理學院/應用數學系/碩士(2006年)

https://doi.org/10.6840/cycu200600185

摘要

於西元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=3,n>=2.節點為n的輪子圖(wheel graph)是由擁有n個節點之圈與圈外另一節點相連接所形成的圖,若在輪子圖外圈的每一邊各增加一節點,則我們稱此圖為齒輪圖(gear graph).兩圖形皆已被證明具有完美標號.在此篇論文中,我們證明C_{6} X P_{2t+1}以及齒輪圖皆具有Alpha標號.

關鍵字

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)<=λ=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.

並列關鍵字

Gear Graphs ； Prism Graphs ； Alpha-labeling

參考文獻

[7] M. Maheo, Strongly Graceful Graphs, Discrete Math., 29(1980), pp. 39-46.

[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.