在圖形的標號問題上，所謂的L(p,q)標號，指的是規定相鄰的點，標號差距至少為p，距離2的點，標號差距至少為q，而L(p,q)標號數，為一個圖在L(p,q)標號中所能使用到的最少標號量。在這樣的定義之下，我們討論一個圖在符合maximum degree ∆ 至少為2α，其中α＝⌈p/q⌉，並且每個邊都轉換成一條長度為3的path的情況下，轉換後的圖，其L(p,q)標號數可以達到理論的下界p+(∆-1)q，並在這樣的基礎之上進一步推廣出一些可以達到理論下界標號數的圖形。
另一方面我們討論在圖形上將點標成一個n個非負整數的集合，並且在定義集合之間的距離之下，定義所謂的n-fold L(p,q)標號及標號數。並且給出了path與cycle的卡氏積圖形的n-fold L(2,1)標號數的精確值或是上下界。

Given a graph G and a function h from E(G) to N, the h-subdivision of G, denoted by G_((h) ), is the graph obtained from G by replacing each edge uv in G with a path P:ux_uv^1 x_uv^2⋯x_uv^(n-1) v, where n=h(uv). When h(e)=c is a constant for all e∈E(G), we use G_((c) ) to replace G_((h) ). For a graph G, an L(p,q)-labeling of G is an function f:V(G)→N∪{0} such that |f(u)-f(v)|≥p if d_G (u,v)=1, and |f(u)-f(v)|≥q if d_G (u,v)=2. A k- L(p,q)-labeling is an L(p,q)-labeling such that no label is greater than k. The L(p,q)-labeling number, denoted by λ_(p,q) (G) is the smallest number k such that G has a k- L(p,q)-labeling. For A,B⊆N∪{0}, define d(A,B)=min⁡{|a-b|:a∈A,b∈B}, an n-fold L(p,q)-labeling of G is an function f:V(G)→{A:A⊆N∪{0},|A|=n} such that d(f(u),f(v))≥p if d_G (u,v)=1, and d(f(u),f(v))≥q if d_G (u,v)=2. A n-fold k- L(p,q)-labeling is an n-fold L(p,q)-labeling such that no label is greater than k. The n-fold L(p,q)-labeling number, denoted by λ_(p,q)^n (G) is the smallest number k such that G has a n-fold k- L(p,q)-labeling.
We prove that λ_(p,q) (G_((3) ) )=p+(Δ-1)q when p≥2q and Δ≥2⌈p/q⌉ and λ_(p,q) (G_((h) ) )=p+(Δ-1)q when p≥2q and Δ≥3⌈p/q⌉ where h(e)≥3 for all e∈E(G). We give a necessary and sufficient condition for λ_2,1^n (C_m □(□(□P_2 )) )=4n+1, we also give bounds and exactly values of λ_2,1^n (C_m □(□(□P_k )) ) and λ_2,1^n (P_m □(□(□P_k )) ).

Introduction 1

Preliminaries 13

L(p,q)-labelings of subdivisions of G 19

n-fold L(2,1)-labeling number of Cartesian products of paths and cycles 33

Conclusion 53

References 55

F. Bazzaro, M. Montassier, A. Raspaud, (d; 1)-total labelling of planar graphs with large girth and high maximum degree, Discrete Math. 307 (2007) 2141-2151.
O. V. Borodin, A. V. Kostochka, D. R. Woodall, Total colorings of planar graphs with large maximum degree, J. Graph Theory 26 (1996) 53-59.
O. V. Borodin, A. V. Kostochka, D. R. Woodall, List edge and list total coloring of multigraphs, J. Combin. Theory Ser. B 71 (1997) 184-204.
O. V. Borodin, A. V. Kostochka, D. R. Woodall, Total colorings of planar graphs
with large girth, Europ. J. Combin. 19 (1998) 19-24.
T. Calamoneri, L(h; k)-labeling problem: a survey and annotated bibliography, Comput. J. 54 (2011) 1344-1371.
F. H. Chang, M. L. Chia, D. Kuo, S. C. Liaw, M. H. Tsai, L(2; 1)-labelings of subdivisions of graphs, Discrete Math. 338 (2015) 248-255.
G. J. Chang and D. Kuo, The L(2; 1)-labeling on graphs, SIAM J. Discrete Math.9 (1996) 309-316.
D. Chen,W.Wang, (2; 1)-total labelling of outerplanar graphs, Discrete Appl. Math.155 (2007) 2585-2593.
D. Gonçalves. On the L(p; 1)-labelling of graphs, Discrete Mathematics and Theoretical Computer Science AE (2005) 81-86.
J. R. Griggs, R. K. Yeh, Labelling graphs with a condition at distance 2, SIAM J.Discrete Math. 5 (1992) 586-595.
F. Havet, M.-L. Yu, (p; 1)-total labelling of graphs, Technical Report 4650, INRIA,2002.
F. Havet, M.-L. Yu, (p; 1)-total labelling of graphs, Discrete Math. 308 (2008) 496-513.
S. Isobe, X. Zhou, T. Nishizeki, Total colorings of degenerated graphs, In ICALP 2001, LNCS 207b, 506-517, 2001.
N. Karst, J. Ochrlein, D. S. Troxell, J. Zhu, L(d; 1)-labelings of the edge-path-replacement by factorization of graphs, J. Comb. Optim. 30 (2015) 34-41.
K. W. Lih, D. D. -F. Liu, W. Wang, On (d; 1)-total numbers of graphs, Discrete Math. 309 (2009) 3767-3773.
D. ü, L(2; 1)-labelings of the edge-path-replacement of a graph, J. Comb. Optim. 26 (2013) 385-392.
D. ü, N. Lin, L(d; 1)-labelings of the edge-path-replacement of a graph, J. Comb. Optim. 26 (2013) 819-831.
M. Montassier, A. Raspaud, (d; 1)-total labelling of graphs with a given maximum average degree, J. Graph Theory 51 (2006) 93-109.
M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math. 9 (1971) 396-402.
N. Vijayadita, On total chromatic number of a graph, J. Lond. Math. Soc 3(2) (1971) 405-408.
M. A. Whittlesey, J. P. Georges, D. W. Mauro, On the -number of Qn and related graphs, SIAM J. Discrete Math. 8 (1995) 499-506.
H. P. Yap, Total Colourings of Graphs. Lecture Notes in Mathematics, vol. 1623, Springer, Berlin, 1996.
R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217-1231.
D. Kuo and J.-H. Yan, On L(2; 1)-labeling of Cartesian products of paths and cycles, Discrete Math. 283 (2004), 137-144.
D. Lü and W. Lin, n-fold L(d; 1)-labelings of the edge-multiplicity-path-replacements, preprint.
W. Lin and P. Zhang, On n-fold L(j; k)- and circular L(j; k)-labeling of graphs. Discrete Appl. Math., 160 (2012) 2452-2461.
C. Schwarz and D. S. Troxell, L(2; 1)-labeling of products of two cycles, Discrete Appl. Math. 154 (2006), 1522-1540.
H. Tang, n-fold-L(2; 1)-labelings of the edge-multiplicity-path-replacements, Ars Comb., 143 (2019) 13-28.
R. K. Yeh, Pair L(2; 1)-labelings of in…nite graphs, Discuss. Math. Graph T., 39 (2019) 257-269.
P. Zhang and W. Lin, Multiple L(j; 1)-labeling of the triangular lattice, J. Comb. Optim., 27 (2014) 695-710.