Graceful Labeling on Grids in 3-Dimensions and 4-Dimensions
Date Issued
2006
Date
2006
Author(s)
Chen, Yi-xian
DOI
en-US
Abstract
優美標號(Graceful labeling)最早是由Rosa在1966年提出。一個graph G上的端點標號(vertex labeling)所指的是一個vertex的函數f對應到一些數值(即標號)，而G上的每一edge xy 被指定一個由f(x)和f(y)所決定的數值。如果這樣的一個f:V-->{0,1,...|E|}是單射，且指定 edge xy 的數值為|f(x)-f(y)|而所有的edge都被指定不同的數值，則f被稱為一個優美標號。
Rosa提出假說猜測所有的tree都有優美標號，這個問題懸宕了四十多年。而除了tree以外許多其他的graph上的優美標號也都有研究結果提出。
我的研究發現，在三維和四維的網格上，只要這個網格的三個邊長(三維)或四個邊長(四維)並非全為奇數也並非全為偶數，則這個網格上存在優美標號。
Graceful labeling was first introduced by Rosa in 1966. A
vertex labeling of a graph G is an assignment f of labels to the vertices of G that induces for each edge (xy) a label
depending on the vertex labels f(x) and f(y). An assignment f is called a graceful labeling of a graph G if f is an injection from the vertices of G to the set{0, 1, ..., |E|}, such that, when each edge (xy) is assigned the label |f(x)-f(y)|, the edge labels are distinct.
Rosa conjectured that all trees are graceful, which is an open question for more than 40 years. Besides the trees, many other graphs have been studied.
My study shows that any grid in 3-dimension and 4-dimension with its lengths not all odd neither all even, is graceful. A formula to give an alpha-labeling on such grids is also given in this
Subjects
優美標號
網格
alpha標號
graceful labeling
grid
alpha labeling
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93922137-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):88bf0c76e714e22d23563a8b9f019124