摘要
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 β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.
图G的L(j,k)标号是图的顶点集到非负整数集的一个映射,使得相邻顶点所对应的整数相差至少为j,距离为2的顶点所对应的整数相差至少为k.对于图G的一个L(j,k)标号f,定义其L(j,k)边跨度为βj,k(G,f)=max{f(x)-f(y) :{x,y}∈E(G)}.图G的L(j,k)边跨度定义为βj,k(G),它是G的所有L(j,k)标号f的L(j,k)边跨度中最小的.图G的实值L(j,k)标号是整数L(j,k)标号的推广,是满足相应的距离一条件和距离二条件的从顶点集到实数集的一个映射.图G的实值L(j,k)标号的边跨度记为βj,k(G).研究了图的实值L(j,k)边跨度和整数L(j,k)边跨度的若干性质,完全确定了所有圈以及完全t-部图的边跨度.
基金
The National Natural Science Foundation of China (No10971025)
