臺灣博碩士論文加值系統

一個圖G=(V,E) 是可以質標的圖，若且唯若存在一個一對一且映成函數 f：VR{ 1, 2, ..., |V |}，使得所有在邊集合E中的邊e={u,v}，gcd（f(u), f(v)）=1。一個可以質標的圖，我們稱之為互質圖。在1978年，Roger Entringer 提出"所有的樹都是互質圖"這個猜測；但是到目前為止，這個猜測還沒有被解出來。在這篇論文中，我們研究互質圖，並證明在點數小於105時，這個猜測是對的。

Let G = (V,E) be a graph. A bijection f : V → {1,2,…,|V |} is called a prime labeling if for each e = {u,v} in E, we have gcd ( f (u) , f (v) ) = 1. A graph admits a prime labeling is called a prime graph. In 1978, Roger Entringer conjectured that every tree is a prime graph. So far, this conjecture is still unsolved. In this thesis, we study the prime labeling and we are able to show that the conjecture is true for trees of order up to 104

Contents
Page
Abstract ( in Chinese )……………………………………………… Ⅰ
Abstract ( in English )……………………………………………… Ⅱ
Acknowledgment…………………………………………….…….. Ⅲ
Contents…………………………………………………………….. Ⅳ
Chapter 1. Preliminaries………………………………………..… 1
1.1. Introduction…………………………………….…………...…… 1
1.2. Basic notions…………………………………………………….. 2
1.3. Coprime graph Sn………………………………………………… 4
1.4. Priliminary results……………………………………………….. 7
Chapter 2. The Main Result…………………………………….. 11
2.1 . Prime labeling of small trees…………………….…………...…. 11
2.2 . Concluding……………………………………………………… 22
Reference……………………………………………………………. 23

Reference
[1] D.E. Flath, Introduction to Number Theory, Wiley Interscience.
[2] H.L. Fu & K.C. Huang, On Prime Labelings, Discrete Math. 127 (1994), 181-186.
[3] S.M. Lee, I. Wui and J. Yeh, On the amalgamation of prime graphs, Bull Malaysian Math. Soc. (2) 11 (1988) 59-67.
[4] H. Salmasian, A Result on the Prime Labelings of Trees, preprint.
[5] D.B. West, Introduction to Graph Theory, Prentice Hall (1996).
[6] T.V. Wimer, S.T. Hedetniemi and R. Laskar, A methodoloby for constructing linear graph algorithms, Congressus Numerantium 50 (1985), 43-60.