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

广义Mycieiski图的L（2，1）标号与可满着色图

作　者: 赵小玲
导　师: 吕长虹
学　校: 华东师范大学
专　业: 运筹学和控制论
关键词: 广义Mycielski图 L(2，1)标号 可满着色图 Halin图
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 13次
引　用: 0次
阅　读: 论文下载
 

内容摘要


图的标号问题是图论中一个重要的研究分支,在现实生活中有着广泛的应用。对于一般图,确定它们的标号数的精确值是NP-hard问题。对于一些特殊图,我们可以探讨它们的标号数的精确值和上下界。本文主要介绍了图的L（2,1）标号问题的研究进展和本人在这方面所作的工作,主要包括以下三个部分:（1）研究了广义Mycielski图的L（2,1）标号数;（2）讨论了具有λ（G）=（?）（G）性质的图的特殊结构;（3）讨论了约束条件推广为三个的图的标号问题。在第一部分中,本文得到了如下一些特殊图的广义Mycielski图的L（2,1）标号数的结论:（1）令Mp（Pn）是路Pn的广义Mycielski图,则λ（Mp（Pn））=4当n=2,p≥2时;λ（Mp（Pn））=5当,n=3,p=2时;λ（Mp（Pn））=6当,n≥3,p≥3时。（2） Mp(K1,n-1)是星图K1,n-1)的广义Mycielski图（n≥4）,则λ(Mp(K1,n-1))=2n-1当p=2时;λ(Mp(K1,n-1))=2n当p≥3时。（3）令Mp（Kn）是Kn的广义Mycielski图,则λ（Mp（Kn））=4当n=2时;λ（Mp（Kn））=3n-2当n≥3时。（4）令Mp（Cn）是圈Cn的广义Mycielski图,则λ（Mp（Cn））=7当,n=3,4,5时。在第二部分中,本文讨论了连续标号问题。在[9]中,吕长虹等人证明了（1）G是一个顶点数n边数m的图,若m≤n-2,则λ（G）=（?）（G）,除非G是一些K2的不交并。（2）G是一个阶数为n的图,若C（G）≥[（n+1）/2],则λ（G）=（?）（G）。这两种具有λ（G）=（?）（G）性质的图均为不连通的图。本文考虑了一些连通图的广义Mycielski图的特殊结构,得到了一类具有λ（G）=（?）（G）性质的连通图。在第三部分中,本文研究了约束条件推广为三个的标号问题。讨论了Halin图和完全图的广义Mycielski图的L（3,2,1）标号数的上界,得到了如下的结论:（1）令G是最大度为△的Halin图,则λ3,2.1（G）≤5△+16。（2）令Mp（Kn）是Kn的广义Mycielski图,则λ3,2,1（Mp（Kn））≤7n-4。

全文目录


论文摘要  6-7
ABSTRACT  7-9
第一章 引言  9-16
  §1.1 图的距离标号问题的由来  9-10
  §1.2 基本概念  10-12
  §1.3 一些相关结论  12-16
第二章 广义Mycielski图的L(2,1)标号  16-26
  §2.1 图的广义Mycielski构造  16-17
  §2.2 路的广义Mycielski图的L(2,1)标号  17-19
  §2.3 星的广义Mycielski图的L(2,1)标号  19-20
  §2.4 完全图的广义Mycielski图的L(2,1)标号  20-22
  §2.5 圈的广义Mycielski图的L(2,1)标号  22-26
第三章 连续的L(2.1)标号  26-32
  §3.1 关于连续标号的一些概念和结论  26-27
  §3.2 具有λ(G)-(?)(G)性质的图的结构  27-32
第四章 推广的标号问题  32-38
  §4.1 L(3,2,1)标号的基本概念  32-34
  §4.2 Halin图的L(3,2,1)标号  34-36
  §4.3 完全图的广义Mycielski图的L(3,2,1)标号  36-38
参考文献  38-41
作者申请硕士学位期间完成的论文  41-42
致谢  42

相似论文

  1. 关于几类图的邻点可区别关联色数的研究,O157.5
  2. 若干图类的强边着色,O157.5
  3. 图的{P_r}-自由着色,O157.5
  4. 伪Halin图的着色,O157.5
  5. 一些图的点邻点可区别全染色,O157.5
  6. K_（4-e）链的边—平衡指数集,O157.5
  7. 基于不动点理论的遗传算法研究,TP18
  8. 广义Petersen图的条件着色和L（2，1）-标号,O157.5
  9. 几类图的（排斥）下整和数,O157.5
  10. 透镜空间上的反定向自同胚,O189.33
  11. 图的D（2）-点可区别及点可区别正常边染色,O157.5
  12. 下整和图与排斥下整和图,O157.5
  13. 关于图的关联色数,O157.5
  14. 关于树的整和数的研究,O157.5
  15. 基于软件体系结构的测试技术,TP311.52
  16. 关于（模，整）和图的几个结果,O157.5
  17. 和图论与分数图论的若干结果,O157.5
  18. 三维军队标号系统的研究与实现,E917
  19. 三维非规则军队标号的研究与实现,E071
  20. 一类优美图,TP301.6

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