图的强边染色问题研究

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:heavenlast
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1736年,瑞士数学家Euler在他的论文中讨论了哥尼斯堡七桥问题,由此诞生了一个全新的数学分支-图论。自从四色猜想被提出之后,图的染色问题就成为了图论的一个很重要的研究课题。图的染色理论在计算机理论、组合最优化、信息化科学和网络设计等方面均有着很重要的应用。图的染色理论有很多分支,如边染色、点染色、面染色和全染色等。其中研究最多,结果也较完善的就是图的边染色。本文旨在讨论图的一种比较特殊的边染色-强边染色。本文主要由五个章节组成,主要内容如下:  在第一章,我们首先给出本文用到的基本概念和记号,接着介绍图的强边染色的研究背景和研究现状,最后给出了本文的主要结果。  在第二章,我们着重研究稀疏图的强边染色问题。Hocquard等人最早是研究了最大度小于或等于3(Subcubic graphs)的稀疏图的强边染色。最近,Bensmail等人研究了最大度为4的稀疏图的强边染色,他们证明了最大度为4并且最大平均度分别小于16/5,10/3,17/5,18/5,19/5的图分别可以用16,17,18,19,20种颜色来强边染色。我们改进了他们的结果,证明了最大度为4并且最大平均度分别小于61/18,7/2,18/5,15/4,51/13的图分别可以用16,17,18,19,20种颜色来强边染色。在这一章的第二部分,我们证明了最大度为4并且最大平均度分别小于8/3,14/5的图分别可以用10,11种颜色来强边染色,并且给出两个图说明这两个最大平均度是接近最优的。  在第三章,我们证明了最大度为Δ(Δ≥6)并且最大平均度小于14/5的图可以用3Δ-1种颜色来强边染色。作为这一结果的一个结论,我们得到最大度为Δ(Δ≥6)并且围长g≥7的平面图可以用3Δ-1种颜色来强边染色,从而改进了Wang的结果:所有最大度为Δ≥6并且围长g≥7的平面图可以用3Δ种颜色来强边染色。  在第四章,我们首先集中精力研究伪Halin图的强边染色问题。伪Halin图是Halin图的一般推广。对Halin图的强边染色的研究,最早是Shiu等人,他们证明了Cubic Halin图强边色数至多是9。最近,Hu等人给出了Halin图的强边染色数的一个上界:每个Δ≥4的Halin图的强边染色数最多是2Δ+1。这一章我们证明了:每个Δ≥4的伪Halin图的强边色数最多是3Δ-2。需要说明的是,这个上界是接近最好可能的界,因为我们找到一个伪Halin图,它的强边色数刚好等于3Δ-3。在这一章的最后,我们将主要探讨K2,3-minor free图的强边色数问题。我们将证明:每个非空K2,3-minor free图的强边色数最多是4Δ-6,并且得到这个界是最好的,因为存在一个非空K2,3-minor free图的强边色数刚好为4Δ-6。  第五章作为本文的结束部分,我们提出了可以进一步考虑的研究问题。
其他文献
不等式在数学各个领域和科学技术中都是不可缺少的基本工具,它不仅在数学中处于独特的地位,也为人们提供了理解数学的一种强有力工具,是现代数学的重要组成部分.此外,在Hilbert空
本文主要研究比以下Q曲率方程广泛的方程正解的存在性,Δ2u+Qu-q=0,x∈R3,其中q>0,Q为R3上的已知函数。  本文的结构安排如下:  第一章,简单介绍了该方程的起源与研究背景,回顾
本论文研究了全空间上的椭圆方程{(λI-Δ)α/2(u(x))=aup(x)+buq(x),u(x)>0,x∈Rn,λ,α,a,b>0;p,q>1,Δ=Σni=1(e)2/(e)x2i.正解的径向对称性与单调性。  本文进一步研究了全
Finsler几何就是度量上没有二次型限制的黎曼几何.伟大数学家黎曼(B.Riemann)早在1854年所作的具有历史意义的就职演说中已考虑了这种情况,但鉴于没有二次型限制后计算上过于
绝对破产问题是近几年来风险理论研究的热门.本文在随机回报风险模型和马氏环境风险模型这两个基本风险模型的基础上,从不同方面进行推广,从而得到了不同的风险模型,并着重研究了分红及Gerber-Shiu函数等破产特征量.主要做了以下两个方面的工作:1、基于门槛分红的随机回报风险模型,将门槛分红推广为阈值分红,并引入绝对破产问题.计算了该风险模型的累积分红折现总量的矩母函数、n阶原点矩、Gerber-Sh
通过对某工程前期传统的照明系统与改造后的智能照明控制系统的耗电数据进行对比分析,佐证智能照明控制系统的节电效果,并对两个系统进行投资分析。 By comparing the power
本文研究是在纯压力驱动的作用下,流体通过柔性微管道中的电动流动以及热传输特性.在壁面处添加具有某种电荷的固定电荷层的微管道被称为柔性微管道.在壁面热流恒定以及热充分发展的条件下,通过采用有限差分法,将先前得到的流向势数值解和速度、电势解析解带入到能量方程,从而获得无量纲温度的数值解,其中,该能量方程是受焦耳热以及粘性耗散影响.然后通过数值计算,进一步研究了焦耳热系数S、聚电解质层厚度d、聚电解质层
学位
本文旨在用变分法研究几类带临界增长的非线性椭圆型方程在(AR)条件缺失的情形下基态解的存在性.全文共分四章:  在第一章中,我们概述了问题的背景及研究现状并简要地介绍了
本文给出了关于车辆牌照的数字图像处理一般过程。其中包括图像模式、图像噪声及去噪过程、图像增强、图像二值化等车牌图像的预处理过程。我们在车牌的定位中主要是运用形态
本文基于组合梯度系统方法研究了非自治Birkhoff系统和Chetaev型非完整系统解的稳定性,并用Matlab计算方法对一类弱非线性耦合非完整系统进行数值模拟,观察系统在相空间中的庞加莱截面图,并判断其动力学行为。首先,介绍了4类基本梯度系统和4类广义梯度系统的微分方程及其性质。其次,构建了一类广义组合梯度系统,将非自治Birkhoff系统和非自治广义Birkhoff系统在一定条件下分别表示成这
学位