互質圖的猜測

Abstract

1980年左右Roger Entringer, 猜測『任何樹都可以互質標示』，廿幾年過去了，進展很小，主要的成果都是在一些特別的例子上標示，對實際的樹，幫助很小。這篇論文首先證明李信明等人的猜測：『很多輪子的集合可以互質標示』，然後證明這篇論文的主要定理『對任何點數小於17的樹，都可以用連續的數標示』；最後，利用這個定理對一般的樹，在一些要求下，給一互質標示。我們相信大部份的樹，都可以藉由這個方法全部加以標示。我們也期待用這個方法，很快地把原猜測解決。

In 1980, Roger Entringer conjectured: every tree has a prime labeling. So far, this conjecture is still unsolved. As a matter of fact, only some special types of trees are verified. In this thesis, we first prove the conjecture by S. M. Lee. et al : the amalgamation of m copies of the wheel Wn that share common center, Wm,n, is prime provided that n is even. Then, in section 2.2 we show the main theorem: every tree with order n(n 16) has a modified prime labeling by using consecutive n integers. Using this theorem we are able to show that more classes of trees are prime. We believe that the idea developed in this thesis can be applied to tackle the conjecture by Roger Entringer.