[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(
)
树和路乘积图的L(s, t)边跨度
)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
- 树和路乘积图的L(s, t)边跨度
- 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.
- 图的L(s, t)-标号的概念来自频道分配问题.设s 和 t是2个非负整数.图G的一个L(s, t)-标号是一个从G的顶点集到整数集的映射, 满足:(1)任意2个相邻顶点对应的整数相差至少为s;(2)任意2个距离为2的顶点对应的整数相差至少为t.给定图G的一个L(s, t)-标号f, f的L(s, t)边跨度定义为max{|f(u)-f(v)|:(u, v)∈E(G)}, 记为βst(G, f).图G的L(s, t)边跨度定义为min{βst(G, f):f取遍图G的所有L(s, t)-标号}, 记为βst(G).设T是一棵最大度为Δ(≥2)的树.证明了:若2s≥t≥0, 则βst(T)=(Δ/2-1)t+s;若0≤2s<t且Δ为偶数, 则βst(T)=(Δ-1)t/2;若0≤2s<t且Δ为奇数, 则βst(T)=(Δ-1)t/2+s.同时完全确定了2条路的笛卡儿乘积图和正四边形格图的L(s, t)边跨度.
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.