立方路的多级距离数

The multi-level distance number for cubic paths

连通图G的多级距离标号(电台标号)是顶点集V(G)到非负整数集{0,1,2,…}的一个映射f,使得对于任意的u,v∈V(G)满足:f(u)-f(v)≥diam(G)+1-d(u,v),其中diam(G)是图G的直径,d(u,v)表示两点u,v之间的距离.映射f的跨度是指max u,v∈V(G){f(u)-f(v)}.图G的多级距离数是指图G的所有多级距离标号的最小跨度.图G的立方是由图G通过在距离不超过3的任两点间添加一条连边构成.本文给出了立方路的多级距离数.

The multi-level distance labeling for a connected graph G,also called the radio labeling,is a mapping f：V（G）→ {0,1,2,…}such that for any u,v∈V（G）,f（u）-f（v） ≥diam（G）＋1-d（u,v）,where diam（G）is the diameter of G,and d（u,v）denote the distance between uand vin G.The span of f is defined as max u,v∈V（G）{f（u）-f（v）}.The multi-level distance number of a graph Gis the minimum span of all multi-level distance labeling for G.The cubic of Gis a graph constructed from G by adding edges between vertices of distance at most three parts in G.In this paper,the multi-level distance number for the cubic path is obtained.