[1] Dai Benqiu, Song Zengmin,. L(d, 1)-labeling of regular tilings [J]. Journal of Southeast University (English Edition), 2005, 21 (1): 115-118. [doi:10.3969/j.issn.1003-7985.2005.01.025]

Copy

L(d, 1)-labeling of regular tilings()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

21

Issue:

2005 1

Page:

115-118

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2005-03-30

Info

Title:

L(d, 1)-labeling of regular tilings

Author(s):

Dai Benqiu;  Song Zengmin

Department of Mathematics, Southeast University, Nanjing 210096, China

Keywords:

regular tiling;  frequency assignment problem;  vertex labeling;  L(d;  1)-labeling;  L(2;  1)-labeling

PACS:

O157.5

DOI:

10.3969/j.issn.1003-7985.2005.01.025

Abstract:

L(d, 1)-labeling is a kind of graph coloring problem from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least d apart while nodes at distance two from each other must receive different colors.We focus on L(d, 1)-labeling of regular tilings for d≥3 since the cases d=0, 1 or 2 have been researched by Calamoneri and Petreschi.For all three kinds of regular tilings, we give their L(d, 1)-labeling numbers for any integer d≥3.Therefore, combined with the results given by Calamoneri and Petreschi, the L(d, 1)-labeling numbers of regular tilings for any nonnegative integer d may be determined completely.

References:

[1] Griggs J R, Yeh R K.Labeling graphs with a condition at distance two [J].SIAM J Discrete Math, 1992, 5(4):586-595.
[2] Hale W K. Frequency assignment:theorem and applications [J].Proceedings of the IEEE, 1980, 68(12):1497-1514.
[3] Chang G J, Ke W T, Kuo D, et al.On L(d, 1)-labelings of graphs [J].Discrete Math, 2000, 220(1-3):57-66.
[4] Calamoneri T, Petreschi R.LAMBDA-coloring of regular tiling [A].In:Proc of First Cologne-Twente Workshop (CTW)[C].Electronic Notes in Discrete Mathematics, 2001, 8.
[5] Georges J P, Mauro D W.Generalized vertex labelings with a condition at distance two [J].Congr Numer, 1995, 109:141-159.
[6] Chang G J, Kuo D.The L(2, 1)-labeling on graphs [J].SIAM J Discrete Math, 1996, 9(2):309-316.
[7] Georges J P, Mauro D W.On the size of graphs labeled with a condition at distance two [J].Graph Theory, 1996, 22:47-57.
[8] Georges J P, Mauro D W, Stein M I.Labeling products of complete graphs with a condition at distance two [J].SIAM J Discrete Math, 2000, 14(1):28-35.
[9] Georges J P, Mauro D W, Whittlesey M.Relating path covering to vertex labelings with a condition at distance two [J]. Discrete Math, 1994, 135:103-111.
[10] Whittlesey M A, Georges J P, Mauro D W.On the λ-number of Q_n and related graphs [J].SIAM J Discrete Math, 1995, 8(4):499-506.
[11] Sakai D. Labeling chordal graphs:distance two condition [J].SIAM J Discrete Math, 1994, 7(1):133-140.

Memo

Memo:

Biographies: Dai Benqiu(1980—), male, graduate;Song Zengmin(corresponding author), male, doctor, professor, zmsong@seu.edu.cn.

Common functions