臺灣博碩士論文加值系統

給定一個圖形G， G的L(d_{1},d_{2};p,q)-labeling
是指一個函數 f:V(G)-->{0,1,2,...,n}使得：在d_{G}(u,v)<=d_{1}的情況下，則 |f(u)-f(v)|>=p；而且，在 d_{G}(u,v)<=d_{2}的情況下，則|f(u)-f(v)|>=q。一個k-L(d_{1},d_{2};p,q)-labeling是指一個 L(d_{1},d_{2};p,q)-labeling f使得 max_{vin V(G)}f(v)<=k。我們把圖形G的L(d_{1},d_{2};p,q)-labeling number,記成符號lambda_{d_{1},d_{2}}^{p,q}(G),是指使得圖形G有一個k-L(d_{1},d_{2};p,q)-labeling的最小數k。
在這篇論文中，我們對於一般的圖形和一些特殊的圖形給了L(d_{1},d_{2};p,q)-labeling number的上界和下界 。當圖形G是一條path，我們也討論圖形G的L(d_{1},d_{2};p,q)-labeling number

Given a graph G, an L(d_{1},d_{2};p,q)-labeling of G is a function f:V(G)-->{0,1,2,...,n} such that |f(u)-f(v)|>= p if d_{G}(u,v)<= d_{1} and
|f(u)-f(v)|>= q if d_{G}(u,v)<= d_{2}. A k-L(d_{1},d_{2};p,q)-labeling is an L(d_{1},d_{2};p,q)-labeling f such that max_{vin V(G)}f(v)<= k.The L(d_{1},d_{2};p,q)-labeling number of G, denoted by lambda_{d_{1},d_{2}}^{p,q}(G), is the smallest number k such that G has a k-L(d_{1},d_{2};p,q)-labeling.
In this thesis, we give the upper bound and lower bound of the L(d_{1},d_{2};p,q)-labeling number for general graphs and some special graphs. We also discuss L(d_{1},d_{2};p,q)-labeling number of G, when G is a paths.

1.Introduction
2.Upper Bound and Lower Bound of the L(d_{1},d_{2};p,q)-labeling Number of Graphs
3.The L(d_{1},d_{2};p,q)-labeling Number of Paths
4.Conclusion

[1] G. J. Chang, W. -T. Ke, D. Kuo, D. D. -F. Liu and
R. K. Yeh, ``On L(d,1)-labelings of graphs,'Disc. Math., to
appear.
[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,' Conger. Numer.109 (1995) 141-159.
[4] J. P. Georges, D. W. Mauro and M. A. Whittlesey,
``Relating path covering to vertex labellings with a condition at distance two,' Discrete Math.135 (1994) 103-111.
[5] J. R. Grigges 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 Theory,to appear.
[8] D. Kuo, ``Graph labelling problems,' Ph. D. Thesis,
Dept. of Applied Math., National Chiao Tung Univ., Hsinchu, Taiwan (1995).
[9] D. D. -F. Liu and R. K. Yeh, ``On distance two
labellings of graphs,'Ars Comb., 47 (1997) 13-22.