关于夏代积年与“五星聚”.pdf

第卷第期经济数学
年月二
关于图的,,升标号问题’
邵振东’刘家壮“
南京大学数学系,江苏,南京,。。
东大学数学研究所,山东,济南,
摘要图的,卜标号是一个从顶点集到非负整数集的函数,使得若,户,则对
一妻若二,,则一夕妻图的,一标号数双是使得有任
的,关标号中的最小数本文将,卜标号问题推广到更一般的情形即,,卜标号问
题,并得出了细分图、、图的几的上界
关键词,关标号,细分图,“图
圣引言
当今世界,信息技术的发展突飞猛进,其通信技术正朝着高性能、多用途和方便用户的方
向迅速发展,无线电频率资料逐渐成为一种紧缺资源,频率分配问题作为一个资源优化配置问
题摆在人们面前
频率分配问题是对每个无线电发射台分配一个频率,使得相互干扰的无线电发射台所分
配的频率的间隔在允许的范围之内于年将此问题归结成图的一染色问题,
染色问题在过去的十年里被广泛地加以研究见」于年提出了在几个不
同地点的无线电发射台有效地分配无线电频率,频率用非负整数表示,从而相近的地点分配到
不同的频率,极相近的地点分配的频率至少相差,从而使得这些频率不会相互干扰
和于年在「」中更精确地提出图的一个,一标号是一个从顶
点集到非负整数集的函数,使得若,妇一,则一妇若,妇
,则一图的一个一,一标号是图的一个,一标号,使得所有标号都
小于等于并且至少有一个达到图的,一标号数,用双表示,是一个使得有一
个一,一标号的最小数
和」于年给出了路尸,,圈。和轮图二的,升标号数之,,义
,,双。的精确值和于年证明了当时,有双,,并给
出了当镇时双,了的精确值,对最大度为△的树, 和证明了久为△
或△他们证明了对一般图的,一标号问题是一完备问题对最大度为乙的一般图
, 和证明了双镇当是一连通时,上界被改进为几镇丁乙一当
的直径为时,有几镇△和猜想对最大度为乙的一般图,有双镇丁
博士后科研启动基金资助项目
收稿日期一一·
一一经济数学第卷
和仁〕于年证明了对最大度为△的一般图,有几镇△
△,但离该猜想还有一定的距离
为更精确地刻画这一问题,本文将,一标号问题推广到更一般的情形即,,一标
号问题,并得出了细分图、图的久。的上界
圣细分图的,,一标号数的上界
我们设是一简单图,并令,必表示中点与点的距离,表示非负整数集
定义任给图,设函数,如果当二,时,有一当
,户时,有一妇当,时,有二一妇,则称为的
,,一标号
定义图的一,,一标号是图的一个,,一标号,使得刘
任
定义图的,,一标号数是一个使得图有一个一,,一标号的最小数
记为久
定义司图的细分,记为,是在图的每条边上插人一个顶点得到的一个顶点
若其既为又为的顶点,则称其为一个旧顶点,否则称其为新顶点我们看到,旧顶点在
中只邻接于新顶点,反之亦然若有个顶点和条边,则有个顶点和
条边
我们现在定义,,妻是在的每条边上插进个新的度点而得到图
以下有关一色数。及顶点一着色的概念见
设的顶点数为,,令,,,一,二一,,为的最小一度点,一以一一饥一,
。一的最小一度点,⋯⋯,一、一,,为的最小一度点,⋯⋯,,一为
的最小一度点然后我们按,,⋯⋯,,的顺序依次使的各个顶点得到最小的一着色,
则有
定理若对图存在一种