[1] 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. [doi:10.3969/j.issn.1003-7985.2007.04.031]
Copy
L(s, t)edge spans of trees and product of two paths(
)
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 23
- Issue:
- 2007 4
- Page:
- 639-642
- Research Field:
- Mathematics, Physics, Mechanics
- Publishing date:
- 2007-12-30
Info
- Title:
- L(s, t)edge spans of trees and product of two paths
- Author(s):
- Niu Qingjie; Lin Wensong; Song Zengmin
- Department of Mathematics, Southeast University, Nanjing 210096, China
- Keywords:
- L(s; t)-labeling; L(s; t)edge span; tree; Cartesian product; square lattice
- PACS:
- O157.5
- DOI:
- 10.3969/j.issn.1003-7985.2007.04.031
- Abstract:
- L(s, t)-labeling is a variation of graph coloring which is motivated by a special kind of the channel assignment problem.Let s and t be any two nonnegative integers.An L(s, t)-labeling of a graph G is an assignment of integers to the vertices of G such that adjacent vertices receive integers which differ by at least s, and vertices that are at distance of two receive integers which differ by at least t.Given an L(s, t)-labeling f of a graph G, the L(s, t)edge span of f, βst(G, f)=max{|f(u)-f(v)|:(u, v)∈E(G)} is defined.The L(s, t)edge span of G, βst(G), is minβst(G, f), where the minimum runs over all L(s, t)-labelings f of G.Let T be any tree with a maximum degree of Δ≥2.It is proved that if 2s≥t≥0, then βst(T)=(Δ/2-1)t+s; if 0≤2s<t and Δ is even, then βst(T)=(Δ-1)t/2; and if 0≤2s<t and Δ is odd, then βst(T)=(Δ-1)t/2+s.Thus, the L(s, t)edge spans of the Cartesian product of two paths and of the square lattice are completely determined.
References:
[1] Griggs J G, 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:theory and applications[J].Proceedings of the IEEE, 1980, 68(12):1497-1514.
[3] Georges J P, Mauro D W.Generalized vertex labeling with a condition at distance two[J].Congr Numer, 1995, 109:141-159.
[4] Georges J P, Mauro D W.Labeling trees with a condition at distance two[J].Discrete Math, 2003, 269:127-148.
[5] 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.
[6] Yeh R K.A survey on labeling graphs with a condition at distance two[J].Discrete Math, 2006, 306:1217-1231.
[7] Calamoneri T.The L(h, k)-labeling problem:a survey and annotated bibliography[J].The Computer Journal, 2006, 49(5):585-608.
[8] Yeh R K.The edge span of distance two labelings of graphs[J].Taiwanese J Math, 2000, 4(4):675-683.
[9] 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.
Memo
- Memo:
- Biographies: Niu Qingjie(1975—), male, graduate;Lin Wensong(corresponding author), male, doctor, associate professor, wslin@seu.edu.cn.