臺灣博碩士論文加值系統

給定一個圖G, G 的L(d,1) 標號是指一個函數 使得在d(u,v)=1 的情況下 ; 而d(u,v)=2的情況下 。 對一個非負整數k，k-L(d,1) 標號是指一個L(d,1)標號f使得 。 我們把圖形G的L(d,1) 標號數，記成符號λ_d(G)，是指使得圖形G有一個k-L(d,1)標號的最小數k。在這篇論文中，我們研究路徑與圈的卡氏積之L(d,1)標號數。給定兩個圖G和H，將G和H的卡式積定義為G□H。
在這篇論文中，我們研究兩個圈圖上的卡氏積之L(d,1)標號數。我們確定λ_d(C_3□C_n)和λ_d(C_4□C_n)。在第二節。在第三節，我們研究λ_3(C_m□C_n) 和λ_4(C_m□C_n)。在第四節，我們做了d>4時，λ_d(C_{2m}□C_{2n})。

An L(d,1)-labeling of a graph G is an assignment f of non-negative integers to vertices of G such that |f(u)-f(v)|≥1 if d(u,v)=2 and |f(u)-f(v)|≥d if d(u,v)=1. For a nonnegative integer k, a k-L(d,1)-labeling is an L(d,1)-labeling such that no label is greater than k. The L(d,1)-labeling number of G is the smallest number k such that G has a k-L(d,1)-labeling. Given two graphs G and H, the Cartesian product of these two graphs, denoted by G□H.
In this paper, we discuss the L(d,1)-labeling number of Cartesian product of two cycles. We determine λ_d(C_3□C_n) and λ_d(C_4□C_n) in section 2. In section 3, we study λ_3(C_m□C_n) and λ_4(C_m□C_n). In section 4, we give λ_d(C_{2m}□C_{2n}) when d>4.

Contents


Acknowledgements I

Abstract (in Chinese) II

Abstract (in English) III

Contents IV

1. Introduction P.1

2. The L(d,1)-labeling number of C_m□C_n when
d>=3 and m=3,4. P.6

3. The L(d,1)-labeling number of C_{2m}□C_{2n} when
d=3,4. P.19

4. The L(d,1)-labeling number of C_{2m}□C_{2n} when
d>4. P.26


Reference P. 34

[1] H.-W. Change, H.-W. Chou., D. Kuo and C.-L. Lin, “Labeling graphs with two distance-constraints.”
[2] G. J. Chang, J.-J. Chen,D. Kuo and S.-C. Liaw, “L(d,1)-labelings of digraphs,” to appear in Discrete Appl. Math..
[3] G. J. Chang and D. Kuo,“The L(2,1)-labeling on graphs,” SIAM J. Discrete Math. 9 (1996), 309-316.
[4] G. J. Chang, W.-T. Ke, D. Kuo, D. D.-F. Lin and R. K. Yeh, “On L(d,1)-labeligs of graphs,” Discrete Mtah. 220(2000),57-66.
[5] G. J. Chang and S.-C. Liaw,“The L(2,1)-labeling problem on ditrees,” Ars Combin. 66 (2003),23-31.
[6] G. J. Chang and C. Lu, “Distance-two labeling of graphs.” European J. Combin. 24 (2003),53-58.
[7] S.H. Chiang and J.H.Yan, “On L(d,1)-labeling for the Cartesian product with a cycle and a path,” submitted.
[8] J.Fiala, T. Kloks and J. Kratochvil, “Fixed-parameter complexity of λ-labelings,” Discrete Appl. Math. 133 (2001), 59-72.
[9] J. Georges and D. W. Mauro, “On the criticality of graphs
labelled with a condition at distance two,” Congr. Numer. 101 (1994), 33-49.
[10] J. Georges and D. W. Mauro, “Generlized vertex labeling with a condition at distance two,” Congr. Numer. 109(1995),141-159.
[11] J. Georges and D. W. Mauro, “On the size of graphs labeled with a condition at distance two,” J. Graph Theory 22 (1996), 47-57.
[12] J. Georges and D. W. Mauro, “Some results on λ_k-numbers of the products of complete graphs,”Congr. Numer. 140 (1999), 141-160.
[13] J. Georges and D. W. Mauro, “On generalized Petersen graphs labeled with a condition at distance two,” Discrete Math. 259 (2002), 311-318.
[14] J. Georges and D. W. Mauro, “On regular graphs optimally labeled with a condition at distance two,”SIAM J. Discrete Math. 17 (2003), no. 2, 320–331.
[15] J. Georges, D. W. Mauro, and M. I. Stein, “Labeling products of complete graphs with a condition at distance two,” SIAM J.Discrete Math. 14 (2000), 28-35.
[16] J. Georges, D. W. Mauro, and M. Whittlesey, “Relating path covering to vertex labellings with a condition at distance two,” Discrete Math. 135 (1994),103-111.
[17] J. R. Griggs and R. K. Yeh, “Labeling graphs with a condition at distance two,” SIAM J. Discrete Math.5 (1992), 586-595.
[18] W. K. Hale, Frequency assignment: theory and applications, Proc. IEEE 68 (1980), 1497-1514.
[19] J.van den Heuvel, R. A. Leese, and M. A. Shepherd, “Graph labeling and radio channel assignment”, J. Graph Theory 29 (1998), 263-283.
[20] P. K. Jha, A. Narayanan, P. Sood, K. Sundaram, and V. Sunder,“On L(2, 1)-labeling of the Cartesian product of a cycle and path,” Ars Combin. 55 (2000), 81-89.
[21] P. K. Jha, “Optimal L(2, 1)-labeling of Cartesian products of cycles with an application to independent domination,” IEEE Trans. Circuits Systems I : Fundamental Theory and Appl. 47 (2000), 1531-1534.
[22] P. K. Jha, Sandi Klavzar and Aleksander Vesel “Optimal L(d, 1)-labeling of Cartesian direct products of cycles and Cartesian products of cycles,” Discrete Appl. Math. 152 (2005), 257-265.
[23] D. Kuo, J.-H. Yan, “On L(2,1)-labelings of Cartesian products of paths and cycles,” Discerete Mtah. 283(2004)137-144.
[24] D. D.-F. Liu, “Hamiltonicity and circular distance two labelings,” Discrete Math. 232 (2001), 163-169.
[25] D. D.-F. Liu, “Sizes of graphs with fix order and spans for circular distance-two labelings,” submitted.
[26] D. D.-F. Liu and R. K. Yeh, “On distance-two labelings of graphs, ” Ars Combin. 47 (1997), 13-22.
[27] D. D.-F. Liu and X. Zhu, “Circular distance two labeling and circular chromatic number,” submitted.
[28] F. S. Roberts, Private communication through J, Griggs (1988).
[29] D. Sakai, “Labeling chordal graphs with a condition at distance two,” SIAM J. Discrete Math. 7 (1994), 133-140.
[30] C. Schwarz and D. S. Troxell, “L(2, 1)-labeling of products of two cycles”, Discrete Appl. Math. 154(2006),1522 - 1540.
[31] M. A. Whittlesey, J. P. Georges, and D. W. Mauro, “On the λ-number of Q_n and related graphs,” SIAM J. Discrete Math. 8 (1995), 499-506.
[32] K.-F. Wu and R. K. Yeh, “Labeling graphs with the circular difference,” Taiwanese J. Math. 4 (2000), 397-405.
[33] R. K. Yeh, “The edge span of distance two labeling of graphs,” Taiwanese J. Math. 4 (2000), 675-683.