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

图的邻强边染色

作　者: 戴韵
导　师: 卜月华
学　校: 浙江师范大学
专　业: 应用数学
关键词: 邻强边染色全染色最大度最小度
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 90次
引　用: 0次
阅　读: 论文下载

内容摘要

图的邻强边染色问题在计算机，网络等领域都有广泛的应用。本学位论文讨论的是图的邻强边染色。用χ′_as（G）表示图的邻强边色数。关于图的邻强边染色，张忠辅等人提出猜测：对于|V（G）|≥3的简单连通图G，且G≠C₅，则χ′_as（G）≤Δ（G）+2。但是目前只知道一些特殊图如树，圈，完全二部图，完全图，Halin图，唯圈图等等的邻强边色数及一些上界。在第二章中我们考虑了一般Mycielski图的邻边强染色的问题。给出具体的5-邻强边染色来证明了圈的一般Mycielski图的邻强边色数为5；还证明了若连通图G（V，E）满足χ′_as（G）≤Δ（G）+2，则χ′_as（M_n（G））≤Δ（M_n（G））+2。在第三章中利用最大度为4，围长大于6的平面图的全色数为5的这个性质，证明了最大度为4且围长至少为8的连通平面图G（V，E）满足猜想。研究了最大度为4的图的邻强边染色的问题得到了最大度为4的连通图G（V，E），有χ′_as（G）≤8。在第四章中我们利用引理：若图G满足性质，对任意δ（G）≤d≤Δ（G），k≥Δ（G）+1，有d（k-d）≥n_d-2，则G有一个k-半点可区别边染色，证明了最小度为δ（G）≥n／2+1且n_Δ≤n／2-1的图G满足猜想。还讨论了一般图的邻强边染色的问题，得到了最大度Δ≥3的连通图G（V，E），有χ′_as（G）≤3Δ（G）-1。

全文目录

摘要  2-3
Abstract  3-5
一、绪论  5-10
  (一)、基本概念  5-6
  (二)、邻强边染色概念、应用背景与研究概况  6-10
二、两类一般Mycielski图的邻强边色数  10-13
三、最大度为4的图的邻强边色数  13-31
四、一般图的邻强边色数  31-40
参考文献  40-42
致谢  42-43
作者在攻读硕士学位期间所做的工作  43-44
学位论文独创性声明  44
学位论文使用授权声明  44

相似论文

若干图类的均匀邻强边染色,O157.5
用于潮流计算的稀疏技术研究,TM744
最大度大于等于7的平面图全染色,O157.5
平面图的全染色,O157.5
一类客户关系管理优化模型及其解决方案研究,TP315
图的泛圈性和点泛圈性,O157.5
无标度和加权网络的搜索问题研究,TP393.01
On a Conjecture about Randi(?) Index,O157.5
大型稀疏线性方程组并行求解及预处理技术研究,TP301.6
图的因子和分数因子,O157.5
乘积图的连通度和容错直径的研究,O157.5
一些图的点邻点可区别全染色,O157.5
若干图类的Smarandachely邻点全染色,O157.5
图的点可区别染色、列表染色和线性染色,O157.5
图的邻点可区分的全染色,O157.5
图的邻点可区别的全染色,O157.5
图的全染色、邻点可区别全染色及分数染色,O157.5
图的（邻）点可区别全染色和分数染色,O157.5
具有k条割边的图的Hosoya指数,O157.5
不含相邻短圈的平面图的全染色,O157.5