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

On the construction of graphs with graceful labeling and α-labeling

紀牧音(Mu-Yin Chi)

指導教授 ： 蔡錫鈞

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.01140

摘要

另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

關鍵字

alpha 標號 ； 優美標號 ； α標號 ； 優美圖

並列摘要

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

並列關鍵字

graceful graph ； alpha labeling ； graceful labeling ； graceful ； α-labeling ； alpha-labeling

參考文獻

[2] C. Bu, D. Zhang, and B. He k-gracefulness of Cnm

[4] C. Barrientos Graceful labelings of chain and corona graphs, Bull. Inst. Combin. Appl., 34 (2002) 17-26.

[5] G. S. Bloom and S. W. Golomb Applications of numbered undirected graphs, Proc. IEEE, 65 (1977) 562-570.

[6] I. Cahit Are all complete binary trees graceful?, The American Mathematical Monthly, Vol.83, No.1(Jan., 1976) 35-37.

[7] S. A. Choudum and S. P. M. Kishore Graceful labellings of the union of paths and cycles, Discrete Math., 206 (1999) 105-117.