[1] Dai Benqiu, Lin Wensong,. Real edge spans of distance two labelings of graphs [J]. Journal of Southeast University (English Edition), 2009, 25 (4): 557-562. [doi:10.3969/j.issn.1003-7985.2009.04.030]

Copy

Real edge spans of distance two labelings of graphs()

Share：

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

Volumn:

25

Issue:

2009 4

Page:

557-562

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2009-12-30

Info

Title:

Real edge spans of distance two labelings of graphs

Author(s):

Dai Benqiu;  Lin Wensong

Department of Mathematics, Southeast University, Nanjing 211189, China

Keywords:

L(j;  k)-labeling;  real L(j;  k)-labeling;  L(j;  k)edge span;  real L(j;  k)edge span;  frequency assignment

PACS:

O157.5

DOI:

10.3969/j.issn.1003-7985.2009.04.030

Abstract:

An L(j, k)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices receive integers which are at least j apart, and vertices at distance two receive integers which are at least k apart. Given an L(j, k)-labeling f of G, define the L(j, k)edge span of f, β_{j, k}, (G, f)=max{|f(x)-f(y)|: {x, y}∈E(G)}. The L(j, k)edge span of G, β_{j, k}, (G)is min β_{j, k}, (G, f), where the minimum runs over all L(j, k)-labelings f of G. The real L(j, k)-labeling of a graph G is a generalization of the L(j, k)-labeling. It is an assignment of nonnegative real numbers to the vertices of G satisfying the same distance one and distance two conditions. The real L(j, k)edge span of a graph G is defined accordingly, and is denoted by (^overβ)_{j, k}, (G). This paper investigates some properties of the L(j, k)edge span and the real L(j, k)edge span of graphs, and completely determines the edge spans of cycles and complete t-partite graphs.

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] Georges J P, Mauro D W. Generalized vertex labelings with a condition at distance two [J]. Congr Numer, 1995, 109: 141-159.
[4] Chang G J, Kuo D. The L(2, 1)-labeling on graphs [J]. SIAM J Discrete Math, 1996, 9(2): 309-316.
[5] 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(1/2/3): 103-111.
[6] Whittlesey M, 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.
[7] Chang G J, Ke W T, Kuo D, et al. On L(d, 1)-labelings of graphs [J]. Discrete Math, 2000, 220(1/2/3): 57-66.
[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] 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.
[10] Yeh R K. The edge span of distance two labelings of graphs [J]. Taiwanese J Math, 2000, 4(3): 397-405.
[11] Feng Guizhen, Song Zengmin. Edge span of L(d, 1)-labeling on some graphs [J]. Journal of Southeast University: English Edition, 2005, 21(1): 111-114.
[12] Niu Qingjie, Lin Wensong, Song Zengmin. L(s, t)edge spans of trees and product of two paths [J]. Journal of Southeast University: English Edition, 2007, 23(4): 639-642.
[13] Griggs J R, Jin X T. Real number graph labelings with distance conditions [J]. SIAM J Discrete Math, 2006, 20(2): 302-327.
[14] Griggs J R, Jin X T. Real number channel assignments for lattices [J]. SIAM J Discrete Math, 2008, 22(3): 996-1021.

Memo

Memo:

Biographies: Dai Benqiu(1980—), male, 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: Dai Benqiu, Lin Wensong. Real edge spans of distance two labelings of graphs[J]. Journal of Southeast University(English Edition), 2009, 25(4): 557-562.

Common functions