臺灣博碩士論文加值系統

The well known Graceful Tree Conjecture(GTC) claimed that all trees
are graceful, which still remains open until today. It was proved in 1999
by H. Broersma and C. Hoede that there is an equivalent conjecture for
GTC that all trees containing a perfect matching is strongly graceful. In
this thesis we verify by extending the above result that there exist infinitely
many equivalent versions of the GTC. More precisely, for a fixed graceful
tree Tk of order k, we show that for each k ≥ 2, the conjecture that all trees
containing a graceful Tk-factor is strongly Tk-graceful is equivalent to the
conjecture that all trees are graceful. More applications are also included
by way of identifying new classes of graceful graphs. In particular we verify
infinitely many equivalent Tk-version conjectures of GTC for those trees of
diameter no more than 2⌈D(Tk)2⌉ + 5, where D(Tk) is the diameter of Tk.

1 Introduction 1
1.1 Preliminary Background . . . . . . . . . . . . . . . . . . . . . 1
1.2 Variants of -Valuations by Rosa . . . . . . . . . . . . . . . . 3
1.3 Results of Broersma and Hoede . . . . . . . . . . . . . . . . . 4
2 Main Results 6
2.1 Graceful Factors and Strongly Gracefulness . . . . . . . . . . . 6
2.2 Infinitely Many Equivalences . . . . . . . . . . . . . . . . . . . 8
3 Applications 12
3.1 Graceful m-Distance Trees . . . . . . . . . . . . . . . . . . . . 12
3.2 Strongly Graceful Trees with Bounded Diameters . . . . . . . 14
3.3 -Labeling and -Factor . . . . . . . . . . . . . . . . . . . . . 15
4 Concluding Remarks 19
4.1 Summary of Results . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Further Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 19

[1] R. E. L. Alfred and B. D. McKay. Graceful and harmonious labeling of
trees. Bull. Inst. Appl. 23, 69-72, 1998.
[2] G. S. Bloom, A Chronology of the Ringel-Kotzig Conjecture and the
Continuing Quest to Call All Trees Graceful, Topics in Graph Theory
(New York, 1977), 32-51, Ann. New York Acad. Sci., 328, New York
Acad. Sci., New York, 1979
[3] M. Burzio and G Ferrarese, The Subdivision of a Graceful Tree is a
Graceful Tree, Discrete Math., 181, 1998, No. 1-3, 275-281
[4] H. J. Broersma and C. Hoede, Another Equivalent of the Graceful Tree
Conjecture, Ars Combin., 51, 1999, 183-192
[5] J.C. Bermond, D. Sotteau, Graph decompositions and G-design, in:
Proc. 5th British Combin. Conf., 1975, Congr. Numer. XV (1976) 53-72.
[6] I. Cahit, Status of graceful tree conjecture in 1989, in: R. Bodendieck, R.
Henn (Eds.), Topics in Combinatorics and Graph Theory, in: Physica,
Heildeberg, 1990.
[7] F. R. K. Chung and F. K. Hwang, Rotatable graceful graphs, Ars Combin.,
11 (1981) 239-250
[8] M. Edwards and L. Howard, A Survey of Graceful Trees, Atlantic Electronic
Journal of Mathematics, Vol. 1, No. 1, 2006
[9] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Comb.
(2012) #DS6.
[10] S. W. Golomb, How to Number a Graph, Graph Theory and Computing,
R. C. Read, ed., Academic Press, New York 1972, 23-37
[11] R. L. Graham and N. J. L. Sloane, On additive bases and harmonious
graphs, SIAM J. Alg. Discrete Math., 1 (1980) 382-404
[12] P. Hrnciar, A. Haviar, All trees of diameter five are graceful, Discrete
Math. 233 (2001) 133-150.
[13] C. Huang, A. Kotzig, A. Rosa, Further results on tree labellings, Utilitas
Math. 21c (1982) 31-48.
[14] D. J. Jin, F. H. Meng, J.G. Wang, The gracefulness of trees with diameter
4, Acta Sci. Natur. Univ. Jilin. (1993) 17-22.
[15] K. M. Koh, D. G. Rogers, T. Tan, Two Theorems on Graceful Trees,
Discrete Math., 25, 1979, No. 2, 141-148
[16] M. Haheo, Strongly Graceful Graphs, Discrete Mathematics 29 (1980)
39-46.
[17] D. Morgan, All Lobsters with Perfect Matchings are Graceful, Electron.
Note. Discrete Math., 11 (2002) 6 pp.
[18] S. Poljak, M. Sura, An algorithm for graceful labeling of a class of symmetrical
trees, Ars. Combin. 14 (1982) 57-66.
[19] G. Ringel, Problem 25, in Theory of Graphs and its Applications, Proc.
Symposium Smolenice 1963, Prague (1964) 162.
[20] A. Rosa, On certain valuations of the vertices of a graph, in: Theory
of Graphs (Proceedings of the Symposium, 1966, Rome), Gordon and
Breach, New York, 1967, pp. 349-355.
[21] G. Sethuraman and J. Heesintha, A New Class of Graceful Lobsters, J.
Combin. Math. Combin. Computing, 67 (2008) 99-109
[22] R. A. Stanton and C. R. Zanke, Labeling of Balanced Trees, Proceedings
of the Forth South-Eastern Conference on Combinatorics, Graph Theory
and Computing, Boca Raton, 1973
[23] D. B. West, Introduction to Graph Theory, 2nd edn. Prentice Hall,
Englewood Cliffs (2001)
[24] S.-L. Zhao, All trees of diameter four are graceful, Ann. New York Acad.
Sci. 576 (1989) 700-706.
[25] B. Yao, H. Cheng, M. Yao, M.-M. Zhao, A Note on Strongly Graceful
Trees, Ars Combin., 92, 2009, 155-169