樹和4-正則圖的互質標記

Abstract

令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.