g-边覆盖染色第一类图的几个充分条件

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:dephibase
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G是一个图,C是一个颜色集.一个图G的正常边染色是给图G的边分配颜色使得G的每个点处不能有相同的颜色出现.一个图G的边覆盖染色是用颜色集C给G的边染色使得每个点处每种颜色至少出现1次.一个图G的g-边覆盖染色是图的边覆盖染色的推广,它是用颜色集C给G的边染色使得每种颜色在每个点v∈V(G)至少出现g(v)次,这里g是从V(G)到正整数集的一个函数.使得G有一个k色的g-边覆盖染色的最大的k称为G的g-边覆盖染色数,记为χgc(G).宋慧敏和刘桂真教授[18]的一个结果表明:任意简单图G有χgc(G)=δg(G)-1 或δg(G),这里δg(G)=minv∈V(G){[d(v)/g(v)]}如果χgc(G)=δg(G),称G为g-边覆盖染色第一类图,否则称G为g-边覆盖染色第二类图.这种确定简单图的g-边覆盖染色数的问题称为g-边覆盖染色的分类问题.本论文主要研究图的g-边覆盖染色的分类问题,我们将张霞和刘桂真教授[26]在2011年给出的边覆盖染色里的结果推广到g-边覆盖染色当中,又将此结果的条件弱化,得到一个g-边覆盖染色第一类图的新的充分条件.该结论推广了宋慧敏和刘桂真教授[18]的一个结论.另外,我们将S.Akbari等人[1]在正常边染色里的一个结果部分推广到g-边覆盖染色当中,得到两个g-边覆盖染色第一类图的充分条件.  本文分为四章进行讨论.  在第一章,介绍研究背景和意义,给出论文中用到的概念和符号,并说明g-边覆盖染色的研究进展和本论文的主要结果.  在第二章,介绍本论文所用到的基本工具,并简要说明它们的作用;列出本论文中用到的重要的引理及其推论.  在第三章,讨论几类关于g-边覆盖染色第一类图并对结论进行证明.  在第四章,给出可进一步研究的问题.  本文的主要结果如下:  定理1 令G是一个简单图,关联一个正整函数g:V(G)→Z+,且δg(G)≥2.若G是弱-δg(G)-可剥离的,那么G是9-边覆盖染色第一类的.  定理2 令G是一个简单图,关联一个正整函数g:V(G)→Z+,且δg(G)≥2.若G不是弱-δg(G)-可剥离的,但G的剩余子图的度恢复图有一个δg(G)色的一般的g-边覆盖染色,那么G是g-边覆盖染色第一类的.  定理3 令G是一个简单图,关联一个正整函数g:V(G)→Z+,且δg(G)≥2,H是G利用弱-δg(G)-可剥离算法剥离若干点后得到的非空子图.如果H的度恢复图有一个δg(G)色的一般的g-边覆盖染色,那么G是g-边覆盖染色第一类图.  定理4 令G是一个连通简单图,关联一个正整函数g:V(G)→Z+.如果Gδg的每个分支都是单圈图或者树,且这些单圈图都不是圈,那么G是g-边覆盖染色第一类的.  定理5 令G是一个连通简单图,关联一个正整函数g:V(G)→Z+如果Gδg的每个分支都是单圈图或者树,至多有一个单圈图是圈且Gδg不是圈,那么G是g-边覆盖染色第一类图.
其他文献
在小学英语教学中单词教学一直是其中的重点和难点,许多教学工作者对其教学展开研究探讨,希望能够找出有效的教学方法.本文首先对当前小学英语单词教学存在的问题展开分析,然
本文主要研究了高维系统中一类伴随Hopf分支的同宿轨道分支问题。首先在鞍-焦点的小邻域内对系统进行适当的简化,再通过极坐标变换将中心流形进行降维处理,将对原来的n维系统的
本文主要研究的是元启发式算法在设施选址问题中的应用。   首先,本文简单介绍了设施选址问题的背景、发展以及研究现状,介绍了一些经典的设施选址问题的模型,包括p-中位问题
随着生物信息学的发展,生物网络理论及应用方面的研究已经成为当前生物数学、信息科学和自动化控制领域的前沿课题.其中,人工神经网络和基因网络的动力学分析一直是研究的热点
教学成绩的高低取决于课堂效率的高低,我们致力于打造高效课堂。然而高效率的学习方法多种多样,其中最为重要的就是合作学习。本文分析了合作学习的内涵,并详细介绍了在不同的教
近日由江苏省文化厅主办的“崔见中国画作品展”在中国美术馆拉开帷幕。本次展览展出了崔见近十年来创作的水墨风景画共计60余件。这些作品均为作者反映各地山川自然风貌的创
本文主要利用变分理论中的集中紧性原理、Brezis-Lieb引理及扰动方法,在一定条件下,证明了三类非线性Schr(o)dinger方程组基态解的存在性.本文主要分四部分:第一部分是绪论;第二部
最小二乘估计在数学,统计学,医学,工程等学科的理论和应用中都占据着不可替代的地位,越来越多的领域都需要借助最小二乘估计法进行深度研究.国内外的许多专家学者也已经对最小二
本文主要研究Hilbert空间上的套代数、Banach空间上的JSL代数以及其上的一类特殊的自反算子代数上的线性映射在某些点处的Lie可导的问题,全文共分四章.   第一章介绍了一些
一、劳动的重要性rn1.劳动是人类生存和发展的基本条件rn劳动创造了世界,也创造了人类本身.我们的祖先、我们自己、我们的后代的生存都离不开劳动.联合国教科文组织在对数十
期刊