雙重條件下圓形冪次圖標號問題之研究

THE STUDY ON LABELING PROBLEM OF THE POWERS OF CYCLES UNDER DOUBLE CONDITIONS

陳顥文(Hao-Wen Chen)

指導教授 ： 張薰文

大同大學/電機資訊學院/應用數學學系所/碩士(2004年)

摘要

圖形標號問題的雙重條件為：對於圖形中，距離在d1 之內的任兩頂點，其標號的差異必須至少為l1；且距離在d2 之內的任兩頂點，其標號的差異必須至少為l2。一圖形的標號值定義為在符合雙重條件下，完成圖形標號所需用到之最小數值；而在雙重條件下圖形的標號問題即在研究圖形的標號值，並提出最佳標號函數；其常用於無線網路之頻道分配上，欲尋找最小所需頻寬，以滿足傳送站間頻率不互相干擾的要求。
在本論文中，我們研究雙重條件下圓形冪次圖的標號問題。一圖形的r 冪次圖是以原圖為底，並將原圖中距離在以內的頂點，加邊連結成為鄰點。研究冪次圖的標號問題，可藉由解決相對應原圖的標號問題延伸而得，因此我們由圓形的標號問題著手。我們首先解決(或l )的情形下，圓形及圓形冪次圖的標號問題；而且我們也同時解決了所有圓形冪次圖的著色數問題。此外，對於相異的、d與相異的l 、l 情形，我們解決了部份圓形的標號問題，並對其餘部份提出標號值的上下界。針對各個結果，我們提出相對應之標號函數，並將結果推廣至圓形冪次圖。最後我們提出一些猜測，並在附錄中詳細證明標號函數的正確性。

關鍵字

著色數 ； 頻道分配問題 ； 標號問題

並列摘要

The double conditions of the labeling problem are as follows. Any two vertices
in a graph with distance no more than (or ) must have the labels with at least
(or ) apart. The labeling number of a graph is defined as the smallest positive
integer such that there exists a labeling satisfying the double conditions. The
labeling problem of a graph is to find its labeling number and optimal labeling functions.
The labeling problem has an important application to the channel assignment problem in the wireless network, which is to find the minimum bandwidth such that the requirements for avoiding inference can be satisfied.

並列關鍵字

channel assignment problem ； chromatic number ； labeling problem

參考文獻

Taiwan (2003).

[1] A. A. Bertossi, C. M. Pinotti, and R. B. Tan, “Channel assignment with separation for interference avoidance in wireless networks,” IEEE Trans. on Parallel and Distributed Systems, 14 (2003) 222-235.

[2] G. J. Chang, W.-T. Ke, D. Kuo, D. D.-F. Liu and R. K. Yeh, “On L(d, 1)-labelings of graphs,” Discrete Math. 220 (2000) 57-66.

[3] G. J. Chang and D. Kuo, “The L(2, 1)-labeling problem on graphs,” SIAM Journal of Discrete Math. 9 (1996) 309-316.

[4] G. J. Chang and C. Lu, “Distance-two labelings of graphs,” European Journal of Combinatorics 24 (2003) 53-58.