臺灣博碩士論文加值系統

令G是一個簡單且有限的圖。我們說一個映成函數從點集合到集合{1,2,...,|G|}是一個互質標記，則對於圖G中的任兩相連接的點所標記的整數都必須是互質的。在 1978 年，Roger Entringer 提出"所有的樹都有互質標記"這個猜測;但是到目前為止，這個猜測還沒有被解出來。
樹是一個二部圖，記做 T_n=(A,B)，其中n為點數。在這篇論文中，我們證明當點數 n>=105 且 min{|A|,|B|}<=pi(n) 成立時，則這一類的樹都有互質標記，其中 pi(n) 是小於等於n的正整數中質數的總數。另外我們也會探討當點數至少11時，是否存在有互質標記的4-正則圖。

Let G be a simple and finite graph. A bijection from its vertex set onto {1,2,...,|G|} is called a prime labelling of G if any two adjacent vertices are labelling by copirme integers. Entringer conjectured that every tree has a prime labelling. In this thesis, we show that a tree T_n=(A,B) of order n>=105 with bipartition (A,B) satisfying min{|A|,|B|}<=pi(n) has a prime labelling, where pi(n) is the number of primes at most n. Moreover, we also study that the existence of a 4-regular graph with prime labelling provided the number of vertices is at least 11.

Abstract (in Chinese) . . . . . . . . . . . . . . . . iii
Abstract (in English) . . . . . . . . . . . . . . . . iv
Acknowledgment . . . . . . . . . . . . . . . . . . . .v
Contents . . . . . . . . . . . . . . . . . . . . . . .vi
1 Preliminaries . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . .1
1.2 Basic notions . . . . . . . . . . . . . . . . . . 3
1.3 Preliminaries results . . . . . . . . . . . . . . 5
2 Main Results . . . . . . . . . . . . . . . . . . . .8
2.1 Prime labelling of trees . . . . . . . . . . . . .8
2.1.1 Idea of proof . . . . . . . . . . . . . . . . . 8
2.1.2 The proof . . . . . . . . . . . . . . . . . . . 11
2.2 Existence of 4-regular graph with prime labelling 17
2.2.1 Idea of construction . . . . . . . . . . . . . .17
2.2.2 Algorithm of construction . . . . . . . . . . . 21
2.3 Concluding remark . . . . . . . . . . . . . . . . 23
Reference. . . . . . . . . . . . . . . . . . . . . . .24
Appendix A. . . . . . . . . . . . . . . . . . . . . . 25
Appendix B. . . . . . . . . . . . . . . . . . . . . . 26

[1] V. Chvatal, "On Hamilton's Ideals." J. Combin. Th. 12, 163-168, 1972.
[2] P. Dusart, Autour de la fonction qui compte le nombre de nombres
premiers, Diss. Universit de Limoges, 1998.
[3] E. Erhart, On prime numbers, Fib. Quart. 26 (1988), 271-274
[4] H. L. Fu and K. C. Huang, On prime labellings, Discrete Math. 127
1994, 181-186.
[5] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935),
26-30.
[6] P. Haxell, O. Pikhurko, and A. Taraz. "Primality of trees," J. Combinatorics
2 (2011): 481500.
[7] S. M. Lee, I. Wui and J. Yeh, On the amalgamation of prime graphs,
Bull Malaysian Math. Soc. (2) 11 (1988) 59-67.
[8] S. H. Lin, A study of prime labelling, M. Sc. Thesis, National Chao
Tung University, 1998.
[9] N. Ramya, K. Rangarajan, and R. Sattanathan, 4-regular graphs and its
prime labeling, IJCGTA, Vol. 5, No. 1, (January-June 2012), pp. 29-40
(2011).
[10] L. Robertson and B. Small (2009). On Newman's conjecture and prime
trees, Integers, 9(2), 117-128.
[11] J. Barkley Rosser; Schoenfeld, Lowell, Approximate formulas for some
functions of prime numbers, Illinois J. Math. 6 (1962), no. 1, 64-94.
[12] H. Salmasian, A result on the prime labelings of trees, Bull. Inst. Combin.
Appl., 28 (2000) 36-38.