L(3; 2; 1)-LABELING FOR CYLINDRICAL GRID: THE CARTESIAN PRODUCT OF A PATH AND A CYCLE
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
An L(3,2,1)-labeling for the graph G=(V,E) is an assignment f of a label to each vertices of G such that |f(u)−f(v)|≥4−k when dist(u,v)=k≤3. The L(3,2,1)-labeling number, denoted by λ3,2,1(G), for G is the smallest number N such that there is an L(3,2,1)-labeling for G with span N. In this paper, we compute the L(3,2,1)-labeling number λ3,2,1(G) when G is a cylindrical grid, which is the cartesian product Pm◻Cn of the path and the cycle, when m≥4 and n≥138. Especially when n is a multiple of 4, or m=4 and n is a multiple of 6, then we have λ3,2,1(G)=11. Otherwise λ3,2,1(G)=12.
Abstract
An L(3,2,1)-labeling for the graph G=(V,E) is an assignment f of a label to each vertices of G such that |f(u)−f(v)|≥4−k when dist(u,v)=k≤3. The L(3,2,1)-labeling number, denoted by λ3,2,1(G), for G is the smallest number N such that there is an L(3,2,1)-labeling for G with span N. In this paper, we compute the L(3,2,1)-labeling number λ3,2,1(G) when G is a cylindrical grid, which is the cartesian product Pm◻Cn of the path and the cycle, when m≥4 and n≥138. Especially when n is a multiple of 4, or m=4 and n is a multiple of 6, then we have λ3,2,1(G)=11. Otherwise λ3,2,1(G)=12.
참고문헌 (18)
- A. A. Bertossi, "Channel assignment with separation for inter-ference avoidence in weierless networks", IEEE Trans. Parall. Distrib. Syst, 14, pp.222~235 (2003)
- A. A. Bertossi, "Approximate L-coloring of trees and interval graphs", Networks, 49(3), pp.204~216
- A. A. Bertossi, "Ecient use of Radio spectrum in weierless networks with channel separation between close stations, dial M for mobility", International ACM workshop, Discrete algorithms and methods for mobile computing (2000)
- T. Calamoneri, "The L(h; k)-labeling problem: A survey and annotated bibliogra-phy", Comp. J, 49, pp.585~608 (2006)
- T. Calamoneri, "The L(h; k)-Labelling Problem: An Updated Survey and Anno-tated Bibliography", Comp. J, 54, pp.1344~1371 (2011)
- T. Calamoneri, "Optimal L(δ1,δ2; 1)- labelling of eight-regular grids", Inform. Pro-cess. Lett., 113, pp.361~364 (2013)
- G. J. Chang, "The L(2; 1)-labeling problem on graphs", SIAM J Dis-crete Math, 9, pp.309~316 (1996)
- M. L. Chia, "L(3; 2; 1) labeling of graphs", Taiwan. J. Math, 15, pp.2439~2457 (2011)
- J. R. Griggs, "Labeling graphs with a condition at distance two", SIAM J. Discrete Math, 5, pp.586~595 (1992)
- W. K. Hale, "Frequency assignment: theory and application", Proc. IEEE, 68, pp.1497~1514 (1980)
- B. M. Kim, "L(3; 2; 1)-labeling for the product of a complete graph and a cycle", Taiwan. J. Math., 19, pp.819~848 (2015)
- B. M. Kim, "Distance three labelings for direct products of three complete graphs", Taiwan. J. Math, 17, pp.207~219 (2013)
- B. M. Kim, "Distance three labellings for Kn × K2", Int. J. Comput. Math., 90(5), pp.906~911 (2013)
- J. Liu, "The L(3; 2; 1)-labeling problem on graphs", Math. Appl, 17, pp.596~602 (2004)
- Z. Shao, "Integer linear programming model and satis ability test reduction for distance constrained labellings of graphs: the case of L(3; 2; 1) la-belling for products of paths and cycles", IET Commun, 7, pp.715~720 (2013)
- Z. Shao, "L(3,2,1) -labeling of triangular and toroidal grids", Cent. Eur. J. Oper. Res, 23, pp.659~673 (2015)
- R. K. Yeh, "A survey on labeling graphs with a condition two", Disc. Math., 306, pp.1217~1123 (2006)
- S. Zhou, "A distance-labelling problem for hypercubes", Discrete Appl. Math, 156(15), pp.2846~2854 (2008)