|Table of Contents|

[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()
树和乘积图的圆L(j, k)-标号数
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
树和乘积图的圆L(j, k)-标号数
Author(s):
Wu Qiong;  Lin Wensong
Department of Mathematics, Southeast University, Nanjing 211189, China
吴琼;  林文松
东南大学数学系, 南京 211189
Keywords:
circular L(j;  k)-labeling number;  tree;  Cartesian product of graphs;  direct product of graphs
圆L(j;  k)-标号数;  树;  笛卡尔乘积图;  直积图
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.
设j, k和m是3个正整数. 给定一个图G. 设f:V(G)→{0, 1, …, m-1}是一个映射. 如果对图G的任意一对相邻顶点u和v都有|f(u)-f(v)|m≥j, 对任意一对距离为二的顶点都有|f(u)-f(v)|m≥k, 其中|a-b|m=min{|a-b|, m-|a-b|}, 则称f是图G的一个圆m-L(j, k)-标号. 使得图G有圆m-L(j, k)-标号的最小的正整数m称为图G的圆L(j, k)-标号数, 记为σj, k, (G). 对任意2个满足j≤k的正整数, 确定了树以及2个完全图的笛卡尔乘积图和直积图的圆L(j, k)-标号数.

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.
Last Update: 2010-03-20