论文部分内容阅读
图论是近几十年来十分活跃的应用数学分支,而图的染色问题已成为图论的重要的组成部分,经典的染色问题诸如点染色,边染色问题已得到深入研究.基于此,数学家们又提出许多新的有意义的染色问题.图的染色问题可看作是一种特殊的图标号问题.图标号问题是一类有广泛应用背景的图论问题,其中一个理论研究背景是频道分配问题[15].假定给出一些无线电发射台,为了避免发射信号互相干扰,我们给它们分配频道时需满足：相邻的电台得到的频道相差至少为2；两个离得近（但不非常近）的电台也要得到不同的频道.作为它的一个变形,Griggs和Yeh在1992年提出了L（2,1）-标号问题[25]并将其推广为L（j,k）-标号问题,L（j,k）-标号问题指的是对点进行标号,而J.P.Georges和D.W.Mauro在他们的文章[26]中首先研究了图的L（j,k）-边标号问题.本文第一章主要介绍了文中涉及的主要概念及符号,并总结了图标号问题的历史与近期发展.本文未加说明的定义及符号参见[2].定义1[2]图G的一个正常k-染色是一个映射c：V（G）→[k],[k]={1,2,…,k},k为正整数,使得相邻的点获得不同的颜色.使G有一个正常染色的最小k值称为G的色数,记为x（G）.定义2[2]图G=（V,E）的一个正常边染色是一个映射f：E（G）→[k],[k]={1,2,…,k},k为正整数,使得对于任意相邻的两条边e1,e2有f（e1）≠f（e2）.使G有一个正常边染色的最小的k值,称为G的边色数,记为x’（G）.Hajo Broersma[16]把对原图G的正常点染色在主干道上加强,提出了一种新的染色—主干道染色（BackBone-coloring）在本文中我们沿用这个思想将图的L(（d,1）-标号和L（j,k）-边标号的条件限制在支撑树上,提出了几种在支撑树上作限制的标号问题,并给出了一般图及几类特殊图的标号数的上界.定义3图G的一个L（d,1）-标号是一个满足下面两个条件的映射c：V（G）→{0,1,2…k},（1）对任意的u,u∈V（G）,若d（u,u）=1,则|c（u）-c（u）|≥d；（2）对任意的u,u∈V（G）,若d（u,u）=2,则|c（u）-c（u）|≥1.当所有的标号都小于等于k时,称图G有一个k-L（d,1）-标号.则使得图G有一个k-L（d,1）-标号的最小的正整数k称为图G的L（d,1）-标号数,记为A（G）.定义4给定一个简单连通图G和G的一棵支撑树T,图G的一个L（d,1）-T标号是一个满足下面三个条件的映射c：V（G）→{0,1,2…k},（1）对任意的u,u∈V（G）,若d（u,u）=1,则|c（u）-c（u）|≥1；（2）对任意的u,u∈V（G）,若dT（u,u）=1,则|c（u）-c（u）|≥d；（3）对任意的u,u∈V（G）,若dG（u,u）=2,则|c（u）-c（u）|≥1.当所有的标号都小于等于k时,则称图G有一个k-L（d,1）-T标号.则使得图G有一个k-L（d,1）-T标号的最小的正整数k称为图G的L（d,1）-T标号数,记为λd.T（G）,我们定义Tλd,T（G）：=maxT{λd,T（G）：G是一个图且T是图G的一棵支撑树}.定义5给定一个简单连通图G和G的一棵支撑树T,图G的一个L’（d,1）-T标号是一个满足下面三个条件的映射c：V（G）→{0,1,2…k},（1）对任意的u,u∈V（G）,若d（u,u）=1,则|c（u）-c（u）|≥1；（2）对任意的u,u∈V（G）,若dT（u,u）=1,则|c（u）-c（u）|≥d；（3）对任意的u,u∈V（G）,若dT（u,u）=2,则|c（u）-c（u）|≥1.当所有的标号都小于等于k时,称图G有一个k-L’（d,1）-T标号.则使得图G有一个k-L’（d,1）-T标号的最小的正整数k称为图G的L’（d,1）-T标号数,记为λ’d,T（G）.我们定义：Tλ’d,T（G）：=maxT{λ’d,T（G）：G是一个图且T是图G的一棵支撑树}.定义6给定一个简单连通图G和G的一棵支撑树T,图G的一个L（p,1T）-点标号是一个满足下面两个条件的映射c：V（G）→{0,1,2…,k},（1）对任意的u,u∈V（G）,若dG（u,u）=1,则|c（u）-c（u）|≥p；（2）对任意的u,u∈V（G）,若dT（u,u）=2,则|c（u）-c（u）|≥1.当所有的标号都小于等于k时,称图G有一个k-L（p,lT）-点标号.使得图G有一个k-L（p,lT）-点标号的最小的正整数k称为图G的L（p,1T）-点标号数,记为λp,1T（G）.定义Tλp,1T（G）=maxT{λp,1T（G）：G是一个图且T是图G的一棵支撑树.｝定理2.1.1对于任意的简单连通图G,其最大度为△,T是G的任意一棵支撑树,则Tλp,1T（G）≤2p△-1.定理2.2.1对任意的简单连通图G,其最大度为△,T是G的任意支撑树,利用树的分层算法将T分为X0,X1,…Xk层,记X1中一点为u,其在T上X0层中的邻点为u1,u2…uj（1≤j≤△-1）,若G中不存在满足下列条件的X0层中的点：其在T上的邻点在x1层中,且dT（u）=dG（uj）=△（j=1,2…△-1）,但u1,u2…u△1在G中不存在边.则Tλp,1T（G）≤2p△-2.定理2.2.2设图G是一个简单连通图,最大度为△,T是G的任意一棵支撑树,且图G的最大度点的邻点中至多有△-2个最大度点,则Tλp,1T（G）≤2p△-2定义-7[26]给定一个简单图G,j,k为正整数,f：E（G）→{0,1,2,…,k},若f满足：（1）对任意e1,e2∈E（G）,d（e1,e2）=1,则|f（e1）-f（e2）|≥j（2）对任意e1,e2∈E（G）,d（e1,e2）=2,则|f（e1）-f（e2）|≥k则f称为G的L（j,k）-边标号.记图G的L（j,k）-边标号数为λ’j,k（G）=min{k|G有一个k-L（j,k）-边标号}.在本文的第三章我们提出了几个新的边标号的定义,并给出了一般图及部分特殊图在这些边标号下的上界.定义8给定一个简单图G和G的一棵支撑树T,k为一正整数,f：E（G）→{0,1,2,…,k},若f满足：（1）对任意e1,e2∈E（G）,dG（e1,e2）=1,则|f（e1）-f（e2）|≥p；（2）对任意e1,e2∈E（G）,dT（e1,e2）=2,则|f（e1）-f（e2）|≥q；则f称为G的L（p,qT）-边标号.记图G的L（p,qT）-边标号数为λ’P,qT（G）=min{k|G有一个k-L（p,qT）-边标号}.定义9给定一个简单图G和G的一棵支撑树T,k为一正整数,f是G的一正常边标号,f：E（G）→{0,1,2,…,k},若f满足：（1）对任意e1,e2∈E（G）,dT（e1,e2）=1,则|f（e1）-f（e2）|≥p；（2）对任意e1,e2∈E（G）,dT（e1,e2）=2,则|f（e1）-f（e2）|≥q；则f称为G的L（pT,qT）-边标号.记图G的L（pT,qT）-边标号数为λ’pT,qT（G）=min{k|G有一个k-L（PT,qT）-边标号}.引理3.1.1[10]对于任意一棵树T,其最大度为△,T是G的任意一棵支撑树,则xi,1（T）≤2△-1,即λi,1（T）≤2△-2.定理3.1.2对于任意简单连通图G,其最大度为△,T是G的任意一棵支撑树,则λi,1T（G,T）≤3△-2.定义10[19]设简单图G=（V（G）,E（G））,V（G）={u1,u2,…,un},M-构造图M（G）的点集和边集是如下定义的：V（G）={u1…,u2’,u1’,u2,…,un’,ω},E（M（G））{u；ωli=1,2,…,n}U{uiuj|uiuj∈E（G）}U{uiujluiuj∈E（G）}.从定义可以看出δ（M（G））=δ（G）+1,△（M（G））=2△（G）或△（M（G））=n,且对任意的ui∈V（M（G））,ui’∈V（M（G））,dM（G）（ui）=2dG（ui）,dM（G）（ui）=dG（ui）+1,dM（G）（ω）=n.M-构造图在研究图染色问题的临界性上有重要应用.定理3.1.3设G是阶为n,最大度为△的图,则G的Mycielski图M（G）存在支撑树T使得：当n≤3△时,λi,1T（M（G）,T）≤2△（M（G））-1；当n>3△时,λi,1T（M（G）,T）≤4/3△（M（G））-1.引理3.1.4对于任意一棵树T,其最大度为△,则λ’p,1（T）≤2p（△-1）.定理3.1.5对于任意简单连通图G,其最大度为△,T是G的任意一棵支撑树,则λ’p,1T（G,T）≤3p△-p-1.引理3.2.1[19]对于任意一棵树T,其最大度为△,λ’2,1（T）≤2△+3.定理3.2.2对于任意简单连通图G,其最大度为△,T是G的任意一棵支撑树,则λ’2T,1T（G,T）≤3△+3.定义11[33]若简单图G=（V（G）,E（G））,V（G）={u1,u2,…,un},定义G’的顶点集和边集如下：V（G’）={u1,u2,…,un,u’1,u’2,…,u,n},E（G’）={uiuj,u’i,u’iu’j,u’iu’j|uiuj∈E（G）},则G’称为图G的点分裂图.由点分裂图的定义可知原图与点分裂图的关系为：△（G’）=2△（G）,δ（G’）=2δ（G）,且对任意的u∈V（G’）,dG’（u）=2dG（u）,u’∈V（G’）,dG’（u’）=2dG（u）.定理3.2.3若图G’为连通图G的点分裂图,则G’存在一棵支撑树T’,使得λ’2T,1T（G’,T’）≤2△（G’）+3.定理3.3.1对于任意简单连通图G,其最大度为△,T是G的任意一棵支撑树,则λ’PT,1T（G,T）≤（2p+1）（△-1）+1.定义12[30]设G1,G2均为简单图,若|Gl|=n1,V（G1）={u1,u2,…,un1},|G2|=n2,V（G2）={u1,u2,…,un2},则笛卡尔乘积图G1×G2的点集和边集定义如下：V（G1×G2）={uiuj|i=l,2,…,n1,j=1,2,…,n2}；E（G1×G2）={（uiuj）（ukul）|uj=ul且（uiuk）∈E（G1）或ui=uk且（ujvl）∈E（G2）,i,k=1,2,…,n1；j,l=1,2,…,n2｝笛卡尔乘积图与原图的关系：△（G1×G2）=△（G1）+△（G2）.定理3.3.2若有简单连通图G1,G2,且最大度满足△（G1）≤△（G2）,则笛卡尔乘积图G1×G2存在支撑树T,使得λ’PT,1T（G1×G2,T）≤（2p+1）△（G1）+△（G2）+1.