东南大学学报（英文版）2007，Vol.23Issue(4)：639-642,4.
树和路乘积图的L(s,t)边跨度
L(s,t) edge spans of trees and product of two paths
摘要
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 if0≤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)-标号/L(s,t)边跨度/树/笛卡儿乘积图/正四边形格图Key words
L(s,t)-labeling/L(s, t) edge span/tree/Cartesian product/square lattice分类
数理科学引用本文复制引用
牛庆杰,林文松,宋增民..树和路乘积图的L(s,t)边跨度[J].东南大学学报（英文版）,2007,23(4):639-642,4.基金项目
The National Natural Science Foundation of China (No. 10671033), Southeast University Science Foundation (No.XJ0607230). （No. 10671033）
