论文部分内容阅读
图的距离2着色来自所谓的频道分配问题：某一区域有若干电台，不同的电台要使用无线电波发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的频道资源。图G的L(j，k)-标号着色是图的L(2，1)-标号着色的推广，它是一个从点集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(v)：v∈V(G)}，即图G的所有L(j，K)。标号着色的最大标号的最小值。G的一个m-(j，K)-圆标号着色是这样的一个函数：v(a)→{0，1，2，…，m-*1)且满足：当u和v相邻时，|f(u)-f(v)|m≥J；当u和v距离为2时，|f(u)-f(v)|m≥k，这里：|x|m=min{|x|，m-|x|}．G所拥有的m-(j，K)-圆标号着色中的最小的m称之为G的σ<,j,k>-数，记之为σ<,j,k>(G)。
在第二章中，在完全图的cartesiaIl积的λ<,j，k>-数的已有研究的基础上，进一步研究。证明了当n>m≥l且n>2m>4时，如果j/k≤m，那么λ<,j，k>(K<,n>×K<,m>×K<,l>)=(nm-1)后；如果j/k≥m，那么λ<,j，k>(K<,n>×K<,m>×K<,l>)=(n-1>j+(m-1)k。当n>m≥l且n=2m>4时，如果j/k≤m-1，那么λ<,j，k>(K<,n>×K<,m>×K<,l>)=(nm-1)k；如果j/k≥m-1，那么λ<,j，k>(K,n>×K<,m>×K<,l>)≤(n-1)(j+k)+(m-1)k。当m≤n<2m时，我们也对λ<,j，k>(K<,n>×K<,m>×K,,l>)做了一些研究。
在第三章中，完全给出了三个完全图的cartesian积的λ<,2，1>-数和σ<,2,1>-数。
在第四章中，探讨了连通度为k的图G的λ-数与其子图G-s的各个连通分支补图的路覆盖数之间的关系，这里S是G的一个k-顶点割。