臺灣博碩士論文加值系統

我們知道，圖形之非負整數的頂點標號，對於在研究無線電頻道之分配的問題上，提供了一個自然的設定方法。假設頂點相對應於傳送站，而它們的標號相對應於無線電頻道。在無線電頻道系統中，為了避免相互間的干擾，每一對頂點在它們可以被分配的標號之間，依據它們的間隔，在標號的差值上有一個限制。
一個圖形G之距離為二的標號，是一個設定在頂點為相鄰及兩單位距離之限制的頂點標號。本篇論文在考慮距離為二的標號上，將會有兩種測量的型態。對於任意正整數d。第一種（使用正規絕對差值）被稱為圖形G的L(d,1)-標號；第二種（使用環狀差值）被稱為圖形G的環狀L(d,1)-標號（或簡稱為c-L(d,1)-標號）。在本論文中，我們將在某些圖形（圈圖、樹圖、聯圖和完全多部圖）上利用L(d,1)-標號去探討c-L(d,1)-標號，並針對兩種標號作比較。
此外，一個圖形G之距離d的標號，也是一個頂點標號，使得對於相鄰頂點之標號的環狀差值至少為d。在本篇論文中，我們只研究奇數n-圈圖Cn的環狀d-標號（或簡稱為c-d-標號）。

It is well-known that the vertex-labelling of graphs , where the labels are non-negative integers , provides a natural setting in which to study problems of radio channel assignment. Vertices correspond to transmitter locations and their labels to radio channels. In order to avoid interference in real radio system , each pair of vertices has , depending on their separation , a constraint on the difference between the labels that can be assigned.
A distance two labelling of a graph G is a vertex-labelling that sets constraints both on adjacent vertices and on vertices of distance two apart. For any position d. Two types of measurements on distance two labellings are considered in this article. One (using the regular absolute difference) is called the L(d,1)-labelling of G ; the other (using the circular difference) is called the circular L(d,1)-labelling of (or c-L(d,1)-labelling in short) of G. In this article , we shall apply the L(d,1)-labelling to investigate the c-L(d,1)-labelling on some graphs (cycles , trees , the join of graphs and the complete multipartite graph) , and then make a comparison in between.
Besides , a circular distance d labelling of a graph G is also a vertex-labelling such that the circular difference of the labels is at least d for adjacent vertices. In this article , we only to investigate the circular d-labelling (or c-d-labelling in short) of an odd n-cycle Cn.

Abstract
Contents
Chapter 1 Fundamental Concepts to Graphs
Chapter 2 Brief on Distance Two Labellings
2.1 Introduction
2.2 Basic Properties
Chapter 3 Circular Labellings on Graphs
3.1 Introduction
3.2 Circular d-labellings on Odd n-cycles
3.3 Circular L(d,1)-labellings and Circular L'(d,1)-
labellings on Graphs
3.3.1 Basic Properties
3.3.2 Circular L(d,1)-labellings on Trees and
Cycles
3.3.3 Circular L'(d,1)-labellings on Joins of
Graphs and Complete Multipartite Graphs
Chapter 4 Conclusion
Bibliography

[1] G. J. Chang , W.-T. Ke , D. Kuo , D. D.-F. Liu and R. K.
yeh , On L(d,1)-labellings of graphs , manuscript.
[2] G. J. Chang and D. Kuo , The L(2,1)-labelling problem on
graphs , SIAM J.Disc.Math. , 9(1996)309-316.
[3] J.P.Georges and D. W. Mauro , Generalized vertex
labellings with a condition at distance two , Congr.
Numer. , 109(1995)141-159.
[4] J. P. Georges , D. W. Mauro and M. A. Whittlesey ,
Relationg path covering to vertex labellings with a
condition at distance two , Disc. Math. , 135(1994).
[5] J. R. Griggs and R. K. Yeh , Labelling graphs with a
condition at distance two , SIAM J. Disc. Math. , 5(1992)
586-595.
[6] W. K. Hale , Frequency assignment : theory and
applications , Proc. IEEE , 68(1980)1497-1514.
[7] J. van den Heuvel , R. A. Leese and M. A. Shepherd , Graph
labelling and radio channel assignment , J. Graph heory ,
to appear.
[8] K. Jonas , Graph coloring analogues with a condition at
distance two : L(2,1)-labellings and list lamda-labellings
, Ph. D. Thesis , Dept. of Math. , Univ. of South Carolina
, Columbia SC(1993).
[9] D. Kuo , Graph labelling problems , Ph. D. Thesis , Dept.
of Applied Math. , National Chiao Tung Univ. , Hsinchu ,
Taiwan(1995).
[10] D. D.-F. Liu , Relating Hamiltonicity and path covering to
distance two labellings of graphs , manuscript.
[11] D. D.-F. Liu and R. K. Yeh , On distance two labellings of
graphs , Ars Comb. , 47(1997)13-22.
[12] F. S. Robetrs , private communication with J. R. Griggs
(1988).
[13] D. Sakai , Labelling chordal graphs with a condition at
distance two , SIAM J. Disc. Math. , 7(1994)133-140.
[14] A. Vince , Star chromatic number , J. Graph Theory , Vol.
12 , No. 4 , (1988)551-559.
[15] M. A. Whittlesey , J. P. Georges and D. W. Mauro , On the
lamda-number of Qn and related graphs , SIAM J. Disc.
Math. , 8(1995)499-506.
[16] R. K. Yeh , The edge span of distance two labellings of
graphs , Taiwanese Journal of Math. , to appear.