臺灣博碩士論文加值系統

給定一個圖形G，G的一個L(3, 2, 1)-標號是一個從G的點集對應到非負整數的函數f，滿足當d(u, v) = 3時，|f(u)-f(v)|?1，當d(u, v) = 2時，|f(u)-f(v)|?2，而且當d(u, v) = 1時|f(u)-f(v) |?3，在一個L(3, 2, 1)-標號中，若標號的最大值不超過k，則稱其為一個k-L(3, 2, 1)-標號，若圖形G的一個L(3, 2, 1)-標號是所有可能的k-L(3, 2, 1)-標號中，k的最小可能值，我們以符號λ_3,2,1 (G)來表示。
在本論文中，我們考慮了幾類圖的L(3, 2, 1)-標號。在第二節，我們給了一些基本性質。第三節裡面給了一般圖與樹狀圖的上界。第四節是有關路徑(path)與迴路(cycle)的Cartesian product。第五節與第六節則考慮了可以一些特別的圖形經由聯集(union)，結合(join)，與日冕運算(Corona)之後的結果。最後，我們決定了一類特別的圖-Sierpin ?ski graphs 的L(3, 2, 1)-標號。

Given a graph G, the L(3,2,1)-labeling of G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(u)-f(v)|>=1 if d(u,v) = 3, |f(u)-f(v)|>=2 if d(u,v) = 2, and |f(u)-f(v) |>=3 if d(u,v) = 1, For a nonnegative integer k, a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k. The L(3,2,1)-labeling number of G, denoted by λ_3,2,1 (G), is the smallest number k such that G has a k-L(3,2,1)-labeling.
In this thesis, we study the L(3,2,1)-labeling numbers of several classes of graphs. We give some basic properties in Section two, and give upper bounds for the L(3,2,1)-labeling numbers of general graphs and trees in Section three. In Section four, we study the L(3,2,1)-labeling number of the Cartesian product of paths and cycles. And in Section five and six, we consider the L(3,2,1)-labeling numbers of those graphs which are obtained from the union, join, and Conora of some special graphs. And, in the last section, we determined the L(3,2,1)-labeling numbers of a special class of graphs-the Sierpin ?ski graphs.

1 Introduction …1
2 Preliminary …3
3 Upper bound of the L(3, 2, 1)-labelings of general graphs and trees …5
4 L(3, 2, 1)-labelings of Cartesian product of paths and cycles …9
5 L(3, 2, 1)-labelings of powers of paths …21
6 L(3, 2, 1)-labelings of union and join of graphs …27
7 L(3, 2, 1)-labelings of Conora of graphs …31
8 L(3, 2, 1)-labelings of Sierpinski graphs …35
9 References…43

[1] H. L. Bodlaender, T. Kloks, R. B. Tan, and J. van Leeuwen, λ-coloring
of graphs, in Lecture Notes Computer Science 1770 (2000), 395-406.
[2] H. L. Bodlaender, T. Kloks, R. B. Tan, and J. van Leeuwen, Approximations
for λ-colorings of graphs, Computer J. (to appear).
[3] A. A. Bertossi, C. M. Pinotti and R.B. Tan, L(2, 1, 1)-Labeling problem
on graphs, In preparation (1999).
[4] A. A. Bertossi, C. M. Pinotti, and R. B. Tan, Channel Assignment
with Separation for Interference Avoidance in Wireless Networks, IEEE
Trans. On Parallel & Distributed System, 14 (2003), 222-234.
[5] T. Calamoneri and R. Petreschi, L(2, 1)-labeling of planar graphs.
DIALM 2001, Proc. 5th Int. Workshop, ACM Press, (2001), 28-33.
[6] T. Calamoneri and R. Petreschi, λ-Labeling of Regular Tiling, Proc. of
1st Cologne-Twente Workshop (CTW), vol. 8, 2001.
[7] T. Calamoneri and R. Petreschi, L(2, 1)-Coloring matrogenic graphs.
LATIN 2002: Theoretical Informatics, Proc. 5th Latin American Symposium,
(2002), 236-247. Lecture Notes in Computer Science vol. 2286,
Springer-Verlag, Berlin.
[8] T. Calamoneri and R. Petreschi, Edge-Clique Graphs and the Lambda-
Coloring Problem, Journal of the Brazilian Computer Society, Special
Issue in honor of Jaime Szwarcfiter’s 60th birthday, (2002).
[9] T. Calamoneri and R. Petreschi, Labeling trees with a condition at distance
two, preprint submitted to Elsevier Science,(2003)
[10] G. J. Chang, J.-J. Chen D. Kuo and S.-C. Liaw, Distance-two labelings
of digraphs, Discrete Appl. Math. 155 (2007), 1007-1013.
[11] 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.
[12] G. J. Chang and D. Kuo, The L(2, 1)-labeling on graphs, SIAM J. Discrete
Math. 9 (1996), 309-316.
[13] G. J. Chang and S.-C. Liaw, The L(2, 1)-labeling problem on ditrees,
Ars Combin. 66 (2003), 23-31.
[14] G. J. Chang C. Lu, Distance-two labelings of graphs, European J. Math.
24 (2003), 53-58.
[15] J. Clipperton, J. Gehrtz, Z. Szaniszlo, and D. Torkornoo, L(3, 2, 1)-
Labeling of Simple Graphs, submitted (2006).
[16] J. Fiala, T. Kloks and J. Kratochvil, Fixed-parameter complexity of
λ-labelings, Discrete Appl. Math. 113 (2001), 59-72.
[17] P. C. Fishburn and F. S. Roberts, Full color theorems for L(2, 1)-
coloring, DIMACS Technical Report 2000-08, (2000).
[18] P. C. Fishburn and F.S. Roberts, Minimal forbidden graphs for L(2, 1)-
coloring, DIMACS Technical Report 2000-32, (2000).
[19] P. C. Fishburn and F. R. Roberts, No-hole L(2, 1)-colorings, Discrete
Appl. Math. 130 (2003), 513-519.
[20] Z. F