臺灣博碩士論文加值系統

優美標號(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

Introduction 4
2 2-Dimensional Grids 6
2.1 Labeling On A Path . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Labeling On Pn X Pm . . . . . . . . . . . . . . . . . . . . . . . . 8
3 3-Dimensional Grids 15
3.1 Labeling on Pn X Pm X P2 . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Pn X Pm X P2k: stack k copies of Pn X Pm X P2 together . . . . . 24
3.3 P2n X P2m X P2k and P2n+1 X P2m+1 X P2k+1 . . . . . . . . . . . 30
4 4-Dimensional Grids 32
4.1 Labeling on Pn X P2m+1 X P2k X Pj . . . . . . . . . . . . . . . . 32
5 Conclusion 36

[1] A. Rosa, On certain valuations of the vertices of a graph, Theory of
Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y.
and Dunod Paris (1967) 349-355.
[2]C. Huang, A. Kotzig and A. Rosa, Further results on tree labellings, Util-
itas Math., 21c (1982) 31-48.
[3]P. Hrnciar and A. Haviar, All trees of diameter ‾ve are graceful, Discrete
Math., 233 (2001) 133-150.
[4]R.E.L. Aldred, Siran and Siran, A note on the number of graceful label-
ings of paths, Discrete Math., 261 (2003) 27-30.
[5]R. Frucht, Graceful numbering of wheels and related graphs, Ann. N.Y.
Acad. Sci., 319 (1979) 219-229.
[6]J. Ayel and O. Favaron, Helms are graceful, Progress in Graph Theory
(Waterloo, Ont., 1982), Academic Press, Toronto, Ont. (1984) 89-92.
[7]Q. D. Kang, Z.H. Liang, Y.Z. Gao and G.H. Yang, On the labeling of
some graphs, J. Combin. Math. Combin. Comput., 22 (1996) 193-210.
[8]V. N. Bhat-Nayak and A. Selvam, Gracefulness of n-cone Cm _ Kc
n , Ars
Combin., 66 (2003) 283-298.
[9]B. D. Acharya and M. K. Gill, On the index of gracefulness of a graph
and the gracefulness of two-dimensional square lattice graphs, Indian J. Math.,
23 (1981) 81-94.
[10]D. Jungreis and M. Reid, Labeling grids, Ars Combin., 34 (1992) 167-182.
[11]R. Frucht and J. A. Gallian, Labeling prisms, Ars Combin., 26 (1988)
69-82.
[12]G. S. Singh, A note on graceful prisms, Nat. Acad. Sci. Lett., 15 (1992)
193-194.
[13]J. Huang and S. Skiena, Gracefully labeling prisms, Ars Combin., 38
(1994) 225- 242.
[14]A. Kotzig, Decomposition of complete graphs into isomorphic cubes, J.
Combin. Theory, Series B, 31 (1981) 292-296.