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

图的L（p，q）-标号问题研究

作　者: 朱海洋
导　师: 郝建修
学　校: 浙江师范大学
专　业: 应用数学
关键词: 图的L(p,q)-标号 L(p,q)-边-标号 边-L(p,q)-数 强边-染色 强边-色数 列表-强边-染色 强边-选择数
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 35次
引　用: 0次
阅　读: 论文下载
 

内容摘要


图的L（p，q）-标号来源于Hale所介绍的频率分配问题作为研究背景。给定图G和两个正整数p≥q，G的一个m-L（p，q）-标号是映射f：V（G）→{0，1，2，…，m}使得对任意x，y∈V（G），若dG（x，y）=1则|f（x）-f（y）|≥p；若dG（x，y）=2则|f（x）-f（y）|≥q，并称λp，q（G）=min{m|存在G的一个m-L（p，q）—标号}为图G的L（p，q）-数。 本学位论文，首先总结近些年图的L（p，q）-标号的主要结果和进展，然后我们兴趣在于最大度△（G）≤4的图G的线图L（G）的L（1，1）-标号和L（2，1）-标号。通常用λ′p，q（G）记线图L（G）的L（p，q）-数。最后，研究某些特殊图类的L（P，q）—标号问题。 线图L（G）的L（1，1）-标号是类似于图G的强边-染色，记SX′（G）(SX′l（G）)为G的强边-色数（列表-强边-色数），那么SX′（G）=λ′1，1（G）+1。在1985年，Erdos和Nesetril提出猜想，令G为简单图，那么当△（G）为偶数时，SX′（G）≤5△2（G）／4；当△（G）为奇数时，SX′（G）≤5△2（G）／4—△（G）／2+1／4。当△（G）=4时，猜想上界是20，Horak证明SX′（G）≤23。当△（G）=3时，猜想上界是10，这个界已被Anderson和Horak独立验证。 本文证明，当△（G）=4时，SX′l（G）≤22。而且，若围长g（G）≤4，则SX′（G）≤21。因为SX′（G）≤SX′l（G），因此这个改进了先前Horak的结果。另外，若△（G）=3，则SX′l（G）≤11。 对于△（G）≤4的图G，Georges和Mauro证明λ′2，1（G）≤2（△（G）-1）（△（G）+2）。本文改进这个上界得到λ′2，1（G）≤2△2（G）-2。 最后，本文研究k-退化图及G1和G2的M-matched sum图G1M+G2的L（p，q）-数。特别的，给出仙人掌图，唯一圈图L（p，1）-数λp，1（G）的可达界。

全文目录


相似论文

  1. 若干图类的均匀邻强边染色,O157.5
  2. 伪Halin图的着色,O157.5
  3. 图的邻强边染色,O157.5
  4. 图上的传播学习研究及应用,TP181
  5. 关于模和图与有向和图,O157.5
  6. 一类优美图,O157.5
  7. 图的脆弱性参数研究,O157.5
  8. 图的L（2，1）-边标号,O157.5
  9. 和图与整和图,O157.5
  10. 几类特殊图的脆弱性参数,TP393.01
  11. 一类优美图,TP301.6
  12. 赋权图的DNA计算模型,O157.5
  13. 复杂布尔网络稳定性问题的研究,O157.5
  14. 复杂网络的建模分析及其应用,O157.5
  15. 复合型均衡网络的存在性及其算法研究,O157.5
  16. 随机网络模型分离,O157.5
  17. 两类图的色等价图,O157.5
  18. 图谱研究的一般方法,O157.5
  19. 基于复杂网络的供应链建模与网络效率研究,O157.5
  20. 几类序列的多重卷积公式,O157.1
  21. 隐马尔科夫模型演化下的隐组检测,O157.5

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