建構有優美標號或α標號的圖

Abstract

另G為一個簡單圖(simple graph)，G上的端點標號(vertex labeling)所指的是一個vertex的函數f對應到一些數值，而G上的每一個edge (u,v) 被指定個由f(x)和f(y)所決定的數值。如果這個fV(G)→{0,1,...,m}為單射，所指定edge (u,v) 的數值為|f(x)–f(y)|，並且所有的edge都被指定不同的數值，則f被稱做是優美標號。如果還另外存在一個邊界數值(boundary value) k，使每一個edge(u,v) 都能滿足f(u)≤k<f(v)或f(v)≤k<f(u)的條件，我們就稱f叫做是α標號。 我們定義兩種圖型 ，並使用建構的方法去建造他們。我們的研究結果也包含了一些目前已知的結果。

Let G be a simple graph with m edges and let f：V(G) → {0,1, ...,m} be an injection. The vertex labeling is called a graceful labeling if every edge (u,v) is assigned an edge label |f(x)–f(y)|and the resulting edge labels are mutually distinct. A graph possessing a graceful labeling is called a graceful graph. With an additional property that there exists an boundary value k so that for each edge (u,v) either f(u)≤k<f(v) or f(v)≤k<f(u), the graceful labeling is called an α−labeling. One approach about graph labeling is to construct larger graphs from smaller graphs which have some required properties. For this, starting with a graph that possesses α- labeling is a common approach. In this thesis, we define new families of graphs and prove that they have graceful labelings or α-labelings. Moreover, our results generalize some previous results.