学位论文 > 优秀研究生学位论文题录展示

图的（p，1）-全标号及图的弱邻点可区分的染色问题

作　者: 孙美姣
导　师: 孙磊
学　校: 山东师范大学
专　业: 应用数学
关键词: (p，1)-全标号 (p，1)-全标号数邻点可区分的边染色邻点可区分的全染色支撑树 T-邻点可区分边染色 T-邻点可区分全染色
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 16次
引　用: 0次
阅　读: 论文下载

内容摘要

图理论是一门非常年轻的学科,在许多的科学领域都有着广泛的应用背景.图的染色问题是图理论的一个重要组成部分,而且许多经典的染色问题诸如点染色和边染色等都已经有了深入的研究.随着科技的进步,在各种新的科技问题的背景之下,许多新的染色问题也被相继提出.在无线电网络中分配传播的波段的问题时,产生了一个频道分配问题.如果几个站点是相邻的,为了避免发射的信号相互干扰,那么在给这些相邻的站点分配频道时,它们得到的频道相差至少为2；而且如果两个站点离得近(但不是非常近),那么分配给它们的频道也需要不同.如果把这个问题转化成图论的染色问题就是Griggs和Yeh提出的L(2,1)-标号问题[4].2000年,G.J.Chang等人把它推广到图的L(p,1)-标号[5].图G的L(p,1)-标号是对G的顶点集的一个整数映射L,使得对任意的顶点u,υ满足：(1)若dG(u,v)=1,则|L(u)-L(v)|≥p；(2)若dG(u,v)=2,则|L(u)-L(v)|≥1,(其中dG(u,v)表示u,v两点之间的距离).一个图G的关联图[6]是指把图G的每一条边用长为2的路代替.图G的关联图的L(p,1)-标号,是对G的一个特别的全染色,这种全染色就是由Havet和Yu提出的(p,1)-全标号[7].设p是一个正整数,图G的一个k-(p,1)-全标号是一个映射f：V(G)∪E(G)→{0,1,…,κ｝,使得：(1)G的任意两个相邻的顶点u,v,有|f(u)-f(v)|≥1；(2)G的任意两条相邻的边e,e’,有|f(e)-f(e’)|≥1；(3)G的任意两个关联的点u和边e,有|f(u)-f(e)|≥p.我们称这样的一个标号叫G的(p,1)-全标号.(p,1)-全标号的跨度是指标号中的最大标号与最小标号的差.G的(p,1)-全标号的最小跨度叫(p,1)-全标号数,记作λPT(G),即λPT(G)=min｛k|G有一个k-(p,1)-全标号｝.图的邻点可区分的边染色(邻强边染色)[8]和邻点可区分的全染色[9]是由张忠辅老师首先提出的,在数据传输问题上有一定的应用背景,但是由于限制的条件比较强目前仅在树,圈,完全图等图类上得到了解决.Hajo Broersma[10]曾经把古典的顶点标号进行变形,把对原图G的限制放松到主干道上,提出了一种新的染色一主干道染色(Back Bone coloring).我们沿用此思想在本文中将邻点可区分的全(边)染色的条件限制在支撑树上,提出了如下两种定义：定义1给定一个简单连通图G,k为一个正整数,f是G的一个正常边染色,f：E(G)→{1,2,…k｝,设、T是G的一棵支撑树,记C(u)={f(uw)|w∈N(u)},如果对任意的uv∈E(T)满足C(u)≠C(v),则f称为G的T-邻强边染色.记XTas(G,T)=min{k|G有一个k-T-邻强边染色｝,定义2给定一个简单连通图G,k为一个正整数,f是G的一个正常全染色,f：V(G)∪E(G)→{1,2,…k｝,设T是G的一棵支撑树,记C(u)={f(u)∪f(uw)|w∈N(u)｝,如果对任意的uv∈E(T),满足C(u)≠C(v),则f称为G的T-邻点可区分的全染色.记XTat(G,T)=min{k|G有一个k-T-邻点可区分的全染色}.显然这两个定义的条件要比张忠辅老师提出的邻点可区分的全(边)染色的定义要弱一些,所以我们称这两种新的染色问题为图的弱邻点可区分的染色问题.在本文的第一章里,我们主要介绍了文章中所涉及的一些概念、术语和符号以及图染色问题的发展情况.在第二章中,我们研究了图的(p,1)-全标号,给出了当p=3,Δ≥9时,全标号的一个上界和特殊图的(p,1)-全标号.第三章中研究了T-邻点可区分的全(边)染色,并给出了这两种染色在任意图上的一个上界,以及在一些具体图类上的上界.定理2.1.5设任意图G,Δ(G)≥9,则λ3T(G)≤2Δ(G)+1.定理2.2.4非正则二部图G,Δ(G)=Δ,且图G的最大度点导出子图包含K1,Δ-1,则λpT(G)=Δ+p,(p≥22).定理3.1.2若图G是连通图,Δ(G)=Δ,则对G的任意支撑树T,χ’Tas(G,T)≤2Δ+1.定理3.1.4若图G是简单连通图,Δ(G)=Δ,T是G的任意一棵支撑树,则χTat(G,T)≤3Δ+2.定义3.2.1若简单图G=(V(G),E(G)),V(G)={v1,v2,…,vn｝,图G’的点集和边集定义如下：V(G’)={v1,v2,…,vn,v1’,v2’,…,vn’｝,E(G’)＝{vivj,vi’vj,vivj’,vi’vj’|vivj∈E(G)｝,则图G’称为图G的点分裂图.根据点分裂图的定义可知,原图和点分裂图满足：Δ(G’)=2Δ(G),δ(G’)=2δ(G)且对任意的v∈V(G’),dG’(v)=2dG(v).定理3.2.1图G’为连通图G的分裂图,则G’存在一棵支撑树T’,使得χ’Tas(G’,T’)≤3/2Δ(G’)+1.定理3.2.2若图G/为连通图G的分裂图,则G’存在一棵支撑树T’,使得χTat(G’,T’)≤5/2Δ(G’)+2.定义3.3.1设G1,G2为简单图,若|G1|=n1,V(G1)={u1,u2,…,un1}|G2|=n2,V(G2)={υ1,u2,…,un2｝,G1×G2的点集和边集定义如下：V(G1×G2)={uivj|i=1,2,…,n1,J=1,2,…,n2｝；E(G1×G2)={(uivj)(ukvl)|vj=vl且(ｕiｕk)∈E(G1)或ui=uk且(vjvl)∈E(G2),i,k=1,2,…,n1；J,ι=1,2,…,n2｝.则G1×G2为G1,G2的笛卡尔乘积图.定理3.3.1若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χ’Tas(G1×G2,T)≤2Δ(G1)+Δ(G2)+1.定理3.3.2若连通图G1,最大度为Δ(G1),连通图G2,最大度为Δ(G2),Δ(G1)≤Δ(G2),则其笛卡尔乘积图G1×G2,存在支撑树T,使得χTat(G1×G2,T)≤3Δ(G1)+2Δ(G2)+2.另外我们还研究了一些特殊图类的T-邻点可区分的全染色和边染色.

全文目录

中文摘要  5-9
英文摘要  9-14
第一章引言  14-19
  1.1 基本符号和概念  14
  1.2 图的染色问题及推广  14-19
第二章图的(p,1)-全标号  19-24
  2.1 图的(3,1)-全标号  19-22
  2.2 特殊图的(p,1)-全标号  22-24
第三章图的弱邻点可区分的染色问题  24-44
  3.1 图的T-邻点可区分全(边)染色的上界  24-26
  3.2 分裂图的T-邻点可区分全(边)染色  26-29
  3.3 笛卡尔乘积图的T-邻点可区分全(边)染色  29-33
  3.4 完全图和完全二部图的T-邻点可区分染色  33-37
  3.5 M-构造图的T-邻点可区分染色  37-44
进一步研究的问题  44-45
参考文献  45-48
在学期间发表的学术论文  48-49
致谢  49

图的（p，1）-全标号及图的弱邻点可区分的染色问题

内容摘要

全文目录

相似论文