简单图的邻和可区别边染色

来源 :山东大学 | 被引量 : 0次 | 上传用户:mahui0503
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
对于图G=(V, E),它的正[k]-边染色指的是G的边集E到颜色集C=[k]={1,2,…,k}的映射ψ,若对于任意两条相互关联的边(∨)e1,e2∈E(G)有ψ(e1)≠ψ(e2),则称ψ是G的正常[k]-边染色,我们用x(G)表示使得G有正常[k]-边染色的最小整数k.给定G的正常[k]-边染色ψ,Sψ(v)表示与v相邻的边的权值和,任意uv∈E(G),有Sψ(u)≠Sψ(v),称染色ψ为图G的邻和可区别的[k]-边染色.我们用x∑(G)表示使得G有邻和可区别的[k]-边染色的最小整数k.G的平均度为Σv∈V(G)d(v)/|V(G)|,记为ad(G).最大平均度mad(G)是G的子图的平均度的最大值.本文主要证明了两个定理:  定理1如果G是不含孤立边的mad(G)<10/3的简单图,那么x∑(G)≤k,其中k=max{△(G)+3,11}.  定理2(1)设G是最大度为△,围长为g的正常平面图,如果g≥5,则x∑(G)≤k,其中k=max{△(G)+3,10}.  (2)设G是最大度为△且不含4-圈的正常平面图,则x∑(G)≤k,其中当△(G)≠10时,k=max{△(G)+3,13},当△(G)=10时,k=max{△(G)+3,14}=14.  本文主要内容具体分为三章展开:  第一章,首先介绍了本文用到的基本定义和符号,其次介绍了相关概念和已得到结果,最后给出了本文要证明的两个定理.  第二章,我们利用权转移方法证明了定理1.  第三章,我们利用欧拉原理及权转移规则构造反例证明了定理2.
其他文献
有理分式函数是简单函数类,虽然比多项式复杂,但用它表示函数时,却比多项式灵活、逼近效果好、更能反映函数的具体特征,因而在数值逼近、函数近似等方面得到了广泛的应用。由于有
云计算是继个人电脑、互联网之后电子信息领域又一次科技浪潮,用户逐渐将自己的数据信息保存到云盘中,既使用方便又减少了自己存储所带来的费用。网络云盘大大降低了用户的存
本文以三阶时滞微分方程为研究对象,通过Lyapunov第二方法,主要研究了几类三阶时滞微分方程的渐近稳定性或全局渐近稳定性,得到了使它们的零解渐近稳定或全局渐近稳定的充分性条
本文研究正则图的笛卡尔乘积图与直接乘积图的限制边连通性,设G是任意连通图,令β(G)=min{|S|:SСE(G)且G-S是个偶图}.图G的一个边割S称为m限制边割,如果G-S不包含阶数小于m的连通分
本文的研究内容来源于国家自然科学基金(70771034):基于非一体化供应链的库存与配送协调模型与方法研究。库存路径问题是在两级供应链系统中同时研究库存与运输两方面问题,货