圖型標號問題

Abstract

圖型標號問題是給圖型的點和(或)邊一些數值，使它滿足一些特定的條件 。圖型標號問題中最有名的大概就是地圖著色問題了，它的歷史可以追溯 到1852年。這個問題在1976年被Appel和Haken所解決。在一百多年的時間 □，這個問題被從許多不同的觀點探討著，也有許多和這個主題有關的有 趣問題已經有了結果。有一些也被應用在圖論的其它問題上。除了地圖著 色問題之外，還有許許多多有趣的圖型標號問題被一再的提出來討論，像 是$L(d,1)$標號問題､誠意標號問題､整數的和圖問題､T著色問題､帶 寬問題､優美標號問題．．．等等。這篇論文所要研究的是上面所提到的 前三個問題。在第二章□，我們討論的是$L(d,1)$標號問題，這個問題的 想法源於頻道設定問題，此問題是在討論如何選定一些頻道，使得那些會 彼此干擾的發信點之間的頻道間隔不在某一個不被容許的集合內， Hale 把這樣的問題變成圖型的$T$著色問題。Robert提出了一個$T$著色問題的 變化問題，他稱之為$L(2,1)$標號問題，後來葉光清把這個問題推廣到$ L(d,1)$標號問題。在這篇論文□，我們考慮了一些特別圖型的 $L(d,1)$ 標號，像是路徑､環路､輪圈､強弦圖､無$P_4$圖和樹狀圖。我們同時 也對一般圖型做了探討，像是最大度數和$L(d,1)$標號值間的關係､兩圖 型的聯集和聯合的$L(d,1)$標號值和原兩圖型本身的$L(d,1)$標號值之間 的關係等等。在第三章我們討論的主題是誠意標號問題，這個問題是優美 標號問題的弱化，Cahit最早考慮這個問題，希望藉著對它的探討來解決 優美樹的猜想，在這篇論文□，我們完全解決了$n$個點的完全圖的任意$ m$個聯集的誠意標號問題。在這篇論文的最後一章，我們討論了整數和圖 值的問題，和圖問題和整數和圖問題都是由Harary所提出的，我們在這最 後一章□證明了毛蟲圖､環路､輪圈的整數和圖值都是 $0$．我們也給出 了完全雙邊圖的整數和圖值。在最後，我們把和圖值和整數和圖值的性質 推廣到一般具有二元交換運算的任意集合$X$上，討論所謂的$X$和圖值。 A labeling problem in a graph $G$ is to assign numbers to vertices and/or edges of $G$ such that certain conditions hold. The most well-known problem probably is the map coloring problem. This problem was solved in 1976 by Appel and Haken. Many interesting results around this subject have been obtained. Besides the map coloring problem, there are many graph labeling problems, e.g., the $L(d,1)$-labeling problem, the cordial labeling problem, the integral sum number problem. This thesis studies the first three problems. In Chapter 2, we study the $L(d,1)$-labeling problem. The original idea of this problem was the channel assignment problem, Hale formulated this problem into the notion of the $T$-coloring of a graph. Roberts proposed a variation of the $T$-coloring problem, which is called the $L(2,1)$-labeling problem. Later, Yeh generalized this problem to the $L(d,1)$-labeling problem. In this thesis, we consider the problem for special graphs, such as paths, cycles, wheels, strongly chordal graphs, cographs, and trees. We also consider some basic properties of general graphs, such as the relations between the maximum degree $\Delta(G)$ and the $L(d,1)$-labeling number $\lambda_d(G)$; the relations between $\lambda_d(G), \lambda_d(H)$, $\lambda_d(G \cup H), \lambda_d(G+ H)$ for arbitrary graphs $G$ and $H$. In Chapter 3, we study the cordial labeling problem. This problem is a weaker version of the graceful labeling problem. In this thesis, we completely determine the cordiality of $mKn$, the union of $m$ copies of the complete graph of order $n$. In Chapter 4, we disscuess the integral sum number problem. The concepts of sum numbers and integral sum numbers were first introduced by Harary. In this thesis, we prove that the integral sum number $\zeta(G)=0$ when $G$ is a caterpilar, cycle, or wheel. We also find the integral sum number of complete bipartite graphs.