关于图的一些荫度问题的研究

来源 :东南大学 | 被引量 : 1次 | 上传用户:zhhs555
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的正常k-全染色是指用k种颜色给V(G)∪E(G)中的元素进行染色,使得任意两个相邻的或相关联的元素均染不同的颜色。使得图G有正常的k-全染色的最小正整数k称为G的全色数,记为x"(G)。类似的,我们可以定义图G的正常点染色和正常边染色,对应的色数分别称为点色数和边色数,分别记为x(G)与x(G)。荫度的概念可以看作是图的一种染色(不一定是正常的),其中每个色类的导出子图是一个森林。本文研究了几种不同的荫度概念:图的线性荫度、线性k-荫度、k-星荫度、全荫度、列表全荫度和强均匀点荫度。主要内容概括如下:  (1)图的线性荫度。一个线性森林是指每个连通分支都是路的森林。图G的线性荫度是指使得G可以分解成m个线性森林的最小正整数m,用la(G)表示。本文确定了完全图与路、完全图与圈,以及两个完全图的笛卡尔积图的线性荫度。  (2)图的线性k-荫度。一个线性k-森林是指每个连通分支都是长度不超过k的路的森林。图G的线性k-荫度是指使得G可以分解成m个线性k-森林的最小正整数m,用lak(G)表示。本文首先研究了两个圈的笛卡尔积图的线性2-荫度,得到了确切的数值。此外,本文研究了几类特殊的平面图,分别给出了这些平面图的线性2-荫度的上界。  (3)图的k-星荫度。一个星是指至多一个顶点的度大于1的树。一个k-星森林是指所有分支都是顶点数不超过k+1的星的森林。使得图G可以分解成m个k-星森林的最小正整数m,称为图G的k-星荫度,用sak(G)表示。本文讨论了最大度不超过3的图和树的k-星荫度的上下界,并给出了两个相关的算法。  (4)图的全荫度和列表全荫度。在图G的一个k-全染色f(不一定是正常的)中,若每个色类的元素在全图中的导出子图是一个森林,则称f是图G的一个无圈k-全染色。使得图G有一个无圈k-全染色的最小正整数k称为图G的全荫度,记为ρ"(G)。对于图G的每个元素x,如果我们都给它指定一个颜色集合L(x),那么我们称L为G的一个列表。设L是G的一个给定的列表,如果存在G的一个无圈全染色f,满足对任意的元素x∈V(G)∪E(G)都有f(x)∈L(x),则称f是G的一个无圈列表全染色。若对于满足|L(x)|≥k的任意可能的列表L,G都有一个无圈列表全染色,则称G是无圈k-全可选的。使得图G是无圈k-全可选的最小正整数k称为图G的列表全荫度,记为ρ"l(G)。这两个概念是Hetherington提出的。此外,他还提出了关于全荫度的猜想:对任何简单图G,均有「△(G)+1/2(])≤ρ"(G)≤「△(G)+2/2(」)。本文完全确定了完全图Kn和完全二部图Kn,n的全荫度,证明以上猜想对这两类图是成立的。对于Halin图,我们给出了其列表全荫度的上界。本文还研究了平面图的全荫度,证明了对于△(G)≥13的平面图和△(G)≥7且不含4-圈的平面图,全荫度猜想都是成立的。  (5)图的强均匀点荫度。设f是图G的顶点的一个t-染色,若每个色类的导出子图的每个分支都是最大度不超过k的树,则称f为图G的一个(t,k)-树染色。设f为图G的一个(t,k)-树染色且任何两种不同颜色所染的顶点数最多相差1,则称f为图G的一个均匀(t,k)-树染色。使得对所有的t≥t,图G都具有均匀(t,k)-树染色的最小正整数t,称作强均匀点k-荫度,记作va≡k(G)。吴建良等人首先提出了这个概念,并且猜想:对任何平面图G,均有va≡∞(G)=O(1)。在本文中,我们首先研究了完全二部图Kn,n的强均匀点1-荫度,得到了一些相关的结果。其次,我们研究了两类特殊的平面图,分别得到了强均匀点∞-荫度的上界,从而证明了吴建良的猜想对这两类平面图是成立的。
其他文献
1、请提前在组委会定下足够面积的展位,做好企业形象宣传计划, 特别注意预留出与观众互动的洽谈和演示区,避免临时发现展位过于拥挤而影响美观和展出效果。 2、根据上海和华
随着社会发展,市场经济带来的竞争机制使得现代企业面临的生存和发展的压力之大是前所未有的.在建筑行业领域内的竞争也随着火爆的房地产市场而“火爆”,如何在这样激烈的竞
学位
网络的无标度特性是复杂网络的一个重大发现,实证研究表明许多现实网络都是无标度网络。由于特殊的拓扑结构,无标度网络具有特殊的容错性和动力学行为。本文主要研究无标度网络
本文进行了如下两部分的工作. 第一章研究了非饱和土壤水流问题的广义迎风差分法.非饱和土壤水的流动是田间均质土壤水分运动的一个简化模型.作为一个重要的气候因子一土壤含
随着我国经济的快速发展,数学在其中扮演着越来越重要的角色,航天事业、航海事业的快速发展都离不开数学.但是,大多数的学生,甚至一些成年人对数学的印象仍然是一堆枯燥乏味
金融经济周期是指经济的周期性的持续性的变化,是由金融体系的传导作用形成的.从微观上来看,基础是金融加速器,信用波动和资产价格波动是金融经济基础的重要关注点.金融经济
SPH(Smoothed Particle Hydrodynamics,光滑粒子流体动力学)方法作为最早的无网格粒子方法,是一种独特的、很有前景的数值方法。它是由Lucy,Monaghan& Gingold于1977年同时独立
据统计,叶片振动是威胁旋转机械安全运行的重要因素之一.汽轮机、航空发动机等旋转类机械的叶片即使处于稳定运行状况下,也会受到各种外部因素的干扰而引发剧烈振动,例如摩擦
在高等数学中,二阶导数的几何意义并没有明确给出。通过对一元函数二阶导数在某个区间的正负,可对函数在此区间内的凹凸性进行判断。这说明一元函数二阶导数与相应曲线的弯曲程