圖形上的標號問題

Abstract

摘 要 圖型標號問題是給圖型的點或邊一些數值，使它滿足一些特定的條件。本論文討論的是L(p,q)標號問題，這個問題源自通訊的頻道設定，是討論如何選定一些頻道，使得那些會彼此干擾的發訊點之間的頻道間隔不在某一個不被容許的集合內，Hale把這樣的問題變成圖型的T著色問題，本論文裡我們討論的則是L(p,q)標號問題，並考慮發生在邊上的最大差值。第二節考慮一些特別的圖型，像是環路，樹狀圖和部分完全圖，第三節討論的是有關圖形的乘積問題，第四節是針對方形和三角形格子圖在最優化標號下發生在邊上的最大差距問題做探討，在最後一節，我們考慮兩個圖型的聯集和交集在邊上的最大差值。

Abstract The problem of determining the edge span of an L(2,1)-labeling of a graph was first investigated by Yeh. In this thesis, we extend his notion to the L(p,q)-labeling. We discuss the L(p,q) edge spans on cycles, trees and complete mutipartite graphs. We present results on Cartesian products of graphs in Section 3. In Section 4, we pay attention to triangular lattices and square lattices. Finally, we consider two operations of graphs, the union and the join of two graphs.