论文部分内容阅读
图的距离2标号问题来自电台的频道分配问题:某一区域有若干电台,不同的电台要使用无线电波发送信号,为了避免信号相互干扰,位置十分接近的电台要使用相差足够远的频道,位置较近的电台要使用有一定相差的频道.将频道分配给电台,目标是在保证信号互不干扰的前提下使用跨度最小的频道资源.对任意正整数j,k(j≥k).图G的L(j,k)一标号是一个从点集V(G)到非负整数集的函数.厂满足条件: (1)当uv∈E(G)时,|f(u)-f(v)|≥J;(2)当d(u,v)=2时,|f(u)-f(v)|≥k.图G的L(j,k)-标号数定义为:λ<,j,K>(G)=min<,f> max{f(u):v∈V(G)},即图G的所有L(J,k)-标号的最大标号的最小值。
本文考虑图的距离2边标号问题.图G边集不空,对任意的边e<,1>,e<,2> ∈E(G),若e<,1>,e<,2>是邻接的,则我们规定d(e<,1>,e<,2>)=1;若e<,1>,e<,2>不邻接,但存在一条边e使得e<,1>,e<,2>与e都是邻接的,则规定d(e<,1>,e<,2>)=2.图G的L(j,k).边标号是一个从边集E(G)到非负整数集的函数f满足条件: (1)|f(e<,1>)-f(e<,2>)|≥j,若d(e<,1>,e<,2>)=1;(2)|f(e<,1>)-f(e<,2>)|≥k,若d(e<,1>,e<,2>)=2.图G的L(j,k)-边标号数定义为:λ<,j,k>(G)=min<,f>maX{f(e):e∈E(G)),即图G的所有L(j,k)-边标号的最大标号的最小值,简单记为λ<,j,k>-数.当j=1,k=1时,L(1,1)-边标号即强边着色;本文主要考虑j=2,k=1的情况.设L(G)为G的线图,则易见λ<,j,k>(G)=λ<,j,k>(L(G))。
本文主要研究几类特殊图的边标号数的上界.在第二章中考虑满足条件:△<,L>(G)=3(其中△<,L>(G)是G的线图的最大度)的图G的L(2,1)一边标号数的上界.当g(G)不超过7(其中g(G)是G的围长)或者G存在奇圈时,给出G的λ<,2,1>数的一个上界8.在第三章中分别给出r一路以及简单平面图的L<,j,k>一边标号数的上界.在本文第四章中讨论了路与路的乘积图P<,m>口P<,n>的λ<,1,1>数与λ<,2,1>-数。确定了P<,m>口P><,n>的λ<,1,1>-数,部分地确定了其λ<,2,1>-数,对于其它情形我们则给出了相应的上界。