標題: 互質圖的研究
A Study of Prime Labeling
作者: 林淑華
Shu-Hua Lin
傅恆霖
Hung-Lin Fu
應用數學系所
關鍵字: 質標;互質圖;prime labeling;prime grap
公開日期: 1998
摘要: 一個圖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
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT870507013
http://hdl.handle.net/11536/64858
顯示於類別:畢業論文