互質圖的研究

Abstract

一個圖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