图的邻和可区别边染色和邻和可区别全染色

来源 :中国矿业大学 | 被引量 : 0次 | 上传用户:heiefei
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
对于图G(V,E),给定一个正整数k,一个正常k边染色是一个映射c:E→{1.2……k},对于任意两条相互关联的边e1,e2∈(G),有c(e1)≠c(e2)。一个正常k全染色是一个映射c:V∪E→{1.2……k},使得每一对相邻的点和相邻的边以及相关联的点和边所对应的值不一样。设c是G的一个正常边染色,对V(G)中任意一点ν,令∑c(ν)代表与v相关联的边的颜色之和,如果对E(G)中的每条边uν,有∑c(u)≠∑c(ν),那么这样一个正常边染色叫做邻和可区别边染色,满足这种染色的最小k值叫做邻和可区别边色数,用χ∑(G)来表示。类似地对于图G(V,E)的正常全染色,对于V(G)中任意一点v,令∑s(ν)代表与v相关联的边的颜色与点v的颜色之和。如果对E(G)中的每条边uν,有∑s(u)≠∑s(ν),那么这样一个正常全染色叫做邻和可区别全染色。满足这种染色的最小k值叫做邻和可区别全色数,用χ∑(G)来表示。  本文主要证明了两个定理,第一个定理,对于不含孤立边的简单图G,如果mad(G)<10/3,那么χ∑≤k,其中,k=max{Δ+2,14}。第二个定理,对于平面图G,如果Δ(G)≥5且g(G)≥5,那么χ∑(G)≤Δ(G)+3。  本文主要内容具体分为四章展开:  第一章,介绍研究领域的相关背景及本文用到的基本概念和研究现状。  第二章,利用欧拉公式及权转移规方法证明了第一个定理。  第三章,利用权转移法规则构造反例证明了第二个定理。  第四章,对本文的结果进行了简单的总结并作了进一步的展望。
其他文献
本文主要研究了广义高继常数与广义光滑模的一些性质.本文组织如下;   首先,讨论了广义高继常数E(α,X)的一些性质,进而得到了Banach空间X具有一致正规结构的两个充分条件
综合评价和决策分析在经济领域和日常生活中具有重要地位,国内外的学者已经提出了很多种综合评价方法。本文在粗糙集及模糊集的特点和优点的基础上,介绍了粗糙集理论和模糊集理
本篇论文主要研究两类耦合的非线性偏微分方程组:广义Zakharov方程组和Klein-Gordon-Zakharov方程组的Dirichlet初边值问题的数值解法。在这里,我们采用高精度的微分求积法求解
混沌动力学是一门新兴的学科,混沌本身是不稳定的,对初值非常敏感。混沌吸引子的存在性由两个条件确定:一是有吸引域,保证吸引子的存在,二是在吸引子上存在混沌行为。本文围绕非线
本文主要研究了两个问题:图的最大亏格以及三类图的1-因子计数.   本文第一部分是关于图的最大亏格的综述.图的最大亏格问题一直以来都是图嵌入理论中的一个重要问题,本文综
本文讨论了一个周期边界条件下的Dirac算子的谱问题,记其中p(x),r(x)∈C[O,π],λ为复参数。   首先研究了特征值的秩与整函数ω(λ)的零点重数一致的问题,进而借助于一个微分恒
变分不等式问题作为描述平衡问题的重要工具,在网络经济,交通规划,对策论,工程管理,以及区域科学等领域有着广泛的应用.目前已提出多种迭代算法求解不同类型的变分不等式问题
本研究针对几乎不可压缩弹性问题,设计Uzawa型有限元方法,克服了其中存在的locking现象。对几乎不可压缩弹性材料,当Lamd系数λ→+∞时,使用低阶协调有限元就会出现有限元近似解
本文研究了Wilson元Neumann-Neumann和BPS预处理方法解椭圆问题.   在第一章,对于带间断系数的二阶椭圆问题,我们提出了Wilson元的Neumann-Neumann型的Schwarz预处理方法
控制系统的稳定性分析是系统分析的重要组成部分,Bezout矩阵是解决线性系统稳定性问题的一个有力工具.近年来随着控制理论的发展,Bezout矩阵及其各种推广在现代线性代数中有着越