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

图的标号问题的研究

作　者: 马巧灵
导　师: 吴建良
学　校: 山东大学
专　业: 运筹学与控制论
关键词: 平面图 标号 标号数 全标号 全标号数
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 92次
引　用: 0次
阅　读: 论文下载
 

内容摘要


本文考虑的图如无特别申明均为简单无向有限图。对于一个图G=G（V（G）,E（G）,ψG）,我们用V（G）≠φ和E（G）表示图的顶点集合和边集合,ψG是联系着G中的边和一对无序顶点之间的关联函数。一个图G,如果可以将它画在平面上,使它的边仅在端点上才能相交,则称图G为可嵌入平面的,或称为平面图。平面图G的这种平面上的画法称为图G的一个平面嵌入,平面图的平面嵌入称为平图。一个平图G把平面划分成若干个连通区域,这些区域的闭包称为G的面。对于ν∈V（G）,我们用dG（ν）表示顶点ν在G中的度数,简记为d（ν）,△（G）和δ（G）分别表示G的最大度和最小度,不会混淆时,也用△和δ表示G的最大度和最小度。G中的途径是一个有限非空的顶点和边的交错序列。如果顶点两两不相同,则称为路.起点和终点相同的路称为闭路,闭路又称为圈。长为k的圈称为k-圈.一个面所关联的边的个数（割边要计算两次）,被称为面的度,用r（f）表示。给定一个平面图G,设函数f:V（G）→Z,如果当d（x,y）=1时,有|f（x）-f（y）|≥p;当d（x,y）=2时,|f（x）-f（y）|≥q,这里p≥q>0的正整数,则称f为G的L（p,q）-标号。图G的k-L（p,q）-标号是图G的一个L（p,q）-标号,使得max{f（ν）|ν∈V（G）}=k。图G的L（p,q）-标号数是一个使得图G有一个k-L（p,q）-标号数的最小数ko记一个图的L（p,q）-的标号为λ（G;p,q）。当q=1时,则称f为G的L（d,1）-标号,图G的L（d,1）-标号数记为:λd（G）;当d=2时,则称f为G的L（2,1）-标号,图G的L（2,1）-标号数记为:λ（G）。图的L（d,1）-全标号是对图的顶点和边进行标号,使得相邻的顶点标不同的号,相邻的边标不同的号,并且顶点与所连的边标号数相差至少为d（d≥2）,图G的L（d,1）-全标号数是一个使得图G有一个L（d,1）-全标号数的最小数k。记一个图的L（d,1）-的全标号为λdT（G）。Griggs和Yeh在[8]猜想对任何最大度为△的图,总有λ（G）≤△2。本文得出了自补图的L（2,1）-标号数的上界:λ（G）≤2△。J.V.D.Heuvel和S.McGuinness[11]证明了如下结论:设G是一个具有最大度△（G）的平面图,那么λ（G;p,q）≤（4q-2）△+10p+38q-24（p≥q的正整数）,本文得出了几类平面图的L（p,q）-标号数的上界:Halin图的L（p,q）-标号数的上界:λ（G;p,q）≤（2q-1）△+6p-4q-1,外平面图的L（p,q）-标号数的上界:λ（G;p,q）≤（2q-1）△+2（2p-1）,高度平面图的L（p,q）-标号数的上界,极大地改进了上述结果。全文共分四章,第一章介绍图论中的基本概念,简单综述图的标号理论发展过程中的一些结果和本文的一些结论;第二章研究了两类图的L（d,1）-标号问题:自补图的L（2,1）-标号数的上界,广义Petersen图的L（d,1）-标号数的上界。第三章研究了几类平面图的L（p,q）-标号问题:Halin图的L（p,q）-标号数的上界,外平面图的L（p,q）-标号数的上界,高度平面图的L（p,q）-标号数的上界;第四章研究了特殊二分图的（2,1）-全标号问题。得出的主要结论有:定理1设G∈PG（n）,则λ（G）=3d+3当且仅当图G同构于Petersen图PG。否则λd（G）≤4d。定理2若图G是最大度为△的n阶自补图,则λ（G）≤2△。定理3图G是一个Halin图,则有λ（G;p,q）≤（2q-1）△+6p-4q-1。定理4设G是最大度为△的外平面图,则λ（G;p,q）≤（2q-1）△+2（2p-1）。定理5设G是|V（G）|≥2的h1-图,则λ（G;p,q）≤（2q-1）△（G）+6（p-q）。定理6设G是|V（G）|≥9的h2-图,那么λ（G;p,q）≤（2q-1）△（G）+8p-6q-1。定理7设d≥2,若m≥4,n≥5,则图Gm×n是第二类的定理8对于图Gm×n,当m=3,n=5时,若d≥3,则图Gm×n是第二类的;若d=2,则图Gm×n是第一类的。定理9对于图Gm×n,当m=4,n=4时,若d≥3,则图Gm×n是第二类的;若d=2时,则图Gm×n是第一类的。定理10当d≥3时,图G3×3,G3×4是第二类的。定理11对于图Gm×n（m=2,n≥4）,当d≥2时,图Gm×n是第二类的。定理12对于图Gm×n（m=2,n=3）,当d=2时,则G是第一类的。当d≥3时,则G是第二类的。定理13对于图Gm×n（m=2,n=2）,当d≥2时,则G2×2是第二类的。在本文的最后,还提出了一些问题,已待进一步研究。

全文目录


中文摘要  5-8
ABSTRACT  8-11
第一章 引言  11-16
  §1.1 基本概念  11-12
  §1.2 图的标号问题的应用背景及研究概况  12-16
第二章 图的L(d,1)-标号问题  16-22
  §2.1 广义的Petersen图的L(d,1)-标号  16-19
  §2.2 自补图的L(2,1)-标号  19-22
第三章 几类平面图的L(p,q)-标号  22-33
  §3.1 Halin图的L(p,q)-标号  22-23
  §3.2 外平面图的L(p,q)-标号  23-26
  §3.3 高度平面图的L(p,q)-标号  26-33
第四章 图的(d,1)-全标号  33-41
  §4.1(d,1)-全标号简介  33-34
  §4.2 二部图的(d,1)-全标号  34-41
参考文献  41-45
致谢  45-47
参与的科研项目与发表的论文  47-48
学位论文评阅及答辩情况表  48

相似论文

  1. 基于GIS_GPS的武警作战指挥系统关键技术研究与实现,E211
  2. 蚁群平面网孔搜索算法在水电仿真软件中的实现,TV7
  3. CTCS-3级列控系统现场测试及辅助工具的研究,U284.48
  4. 纽结与能量,O189.24
  5. 若干平面图支配集问题的核心化研究,O157.5
  6. 平面图的线性荫度和线性2-荫度,O157.5
  7. 关于一些图的定向染色,O157.5
  8. 城市突发公共事件伤员救治出救点选择与车辆路径集成优化研究,X928.04;U116.2
  9. 循环圈算术标号的研究,O157.5
  10. 关于路、圈并图优美性的研究,O157.5
  11. 关于DNA图及其标号图的研究,O157.5
  12. 最大度为6的平面图的全染色,O157.5
  13. 关于图的均匀染色,O157.5
  14. 平面图的全可选和3-染色,O157.5
  15. 平面图的边列表染色和线性染色,O157.5
  16. A（m，n）图的顶点优美标号及超顶点优美标号的研究,O157.5
  17. 两类毛毛虫的多级距离数,O157.5
  18. 跳图的平面性,O157.5
  19. 两类4-正则图的最小折数纵横扩张,O157.5
  20. 若干图类的强边着色,O157.5
  21. 图的圆色数的若干结果,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com