CAJ | 학술논문

图的L(s,t)-标号的概念来自频道分配问题.设s和t是2个非负整数.图G的一个L(s,t)-标号是一个从G的顶点集到整数集的映射,满足:①任意2个相邻顶点对应的整数相差至少为s;②任意2个距离为2的顶点对应的整数相差至少为t.给定图G的一个L(s,t)-标号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)边跨度.
도적L(s,t)-표호적개념래자빈도분배문제.설s화t시2개비부정수.도G적일개L(s,t)-표호시일개종G적정점집도정수집적영사,만족:①임의2개상린정점대응적정수상차지소위s;②임의2개거리위2적정점대응적정수상차지소위t.급정도G적일개L(s,t)-표호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)변과도.
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.