[1] Wu Qiong, Lin Wensong,. Circular L(j, k)-labeling numbers of trees and products of graphs [J]. Journal of Southeast University (English Edition), 2010, 26 (1): 142-145. [doi:10.3969/j.issn.1003-7985.2010.01029]

Copy

Circular L(j, k)-labeling numbers of trees and products of graphs()

Share：

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

Volumn:

26

Issue:

2010 1

Page:

142-145

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2010-03-30

Info

Title:

Circular L(j, k)-labeling numbers of trees and products of graphs

Author(s):

Wu Qiong;  Lin Wensong

Department of Mathematics, Southeast University, Nanjing 211189, China

Keywords:

circular L(j;  k)-labeling number;  tree;  Cartesian product of graphs;  direct product of graphs

PACS:

O157.5

DOI:

10.3969/j.issn.1003-7985.2010.01029

Abstract:

Let j, k and m be three positive integers, a circular m-L(j, k)-labeling of a graph G is a mapping f: V(G)→{0, 1, …, m-1}such that |f(u)-f(v)|_m≥jm≥j if u and v are adjacent, and |f(u)-f(v)|_m≥km≥k if u and v are at distance two, where |a-b|_m=min{|a-b|, m-|a-b|}. The minimum m such that there exists a circular m-L(j, k)-labeling of G is called the circular L(j, k)-labeling number of G and is denoted by σ_{j, k}, (G). For any two positive integers j and k with j≤k, the circular L(j, k)-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.

References:

[1] Hale W K. Frequency assignment: theory and applications [J]. Proceedings of the IEEE, 1980, 68(12): 1497-1514.
[2] Griggs J R, Yeh R K. Labeling graphs with a condition at distance 2 [J]. SIAM J Discrete Math, 1992, 5(4): 586-595.
[3] Calamoneri T. The L(h, k)-labeling problem: a survey and annotated bibliography [J]. The Computer Journal, 2006, 49(5): 585-608.
[4] Bertossi A A, Bonuccelli M A. Code assignment for hidden terminal interference avoidance in multihop packet radio networks [J]. IEEE/ACM Transtractions on Networking, 1995, 3(4): 441-449.
[5] Calamoneri T, Pelc A, Petreschi R. Labeling trees with a condition at distance two [J]. Discrete Math, 2006, 306(14): 1534-1539.
[6] Jin X T, Yeh R K. Graph distance-dependent labeling related to code assignment in computer networks [J]. Naval Research Logistics, 2005, 52(2): 159-164.
[7] Heuvel J, Leese R A, Shepherd M A, Graph labeling and radio channel assignment [J]. J Graph Theory, 1998, 29(4): 263-283.
[8] Liu D D F. Hamiltonicity and circular distance two labelings [J]. Discrete Math, 2001, 232(1/2/3): 163-169.
[9] Wu K, Yeh R K. Labelling graphs with the circular difference [J]. Taiwanese J Math, 2000, 4(3): 397-405.
[10] Leese R A, Noble S D. Cyclic labellings with constraints at two distances [J]. The Electronic J of Combin, 2004, 11(1): R16.
[11] Liu D D F, Zhu X. Circulant distant two labeling and circular chromatic number [J]. Ars Combin, 2003, 69(2): 177-183.
[12] Lam P C B, Lin W, Wu J. L(j, k)-labellings and circular L(j, k)-labellings of products of complete graphs [J]. J Combin Optim, 2007, 14(2/3): 219-227.
[13] Lü Damei, Lin Wensong, Song Zengmin. L(2, 1)-circular labelings of Cartesian products of complete graphs [J]. J of Mathematical Research and Exposition, 2009, 29(1): 91-98.
[14] Georges J P, Mauro D W, Stein M I. Labelling products of complete graphs with a condition at distance two [J]. SIAM J Discrete Math, 2000, 14(1): 28-35.

Memo

Memo:

Biographies: Wu Qiong(1985—), female, graduate; Lin Wensong(corresponding author), male, doctor, associate professor, wslin@seu.edu.cn.
Foundation item: The National Natural Science Foundation of China(No.10971025).
Citation: Wu Qiong, Lin Wensong. Circular L(j, k)-labeling numbers of trees and products of graphs[J]. Journal of Southeast University(English Edition), 2010, 26(1): 142-145.

Common functions