Cayley图的彩虹连通数

来源 :南开大学 | 被引量 : 0次 | 上传用户:lz274458795
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
2008年,Chartrand等人率先引入并研究了图的彩虹连通数,他们确定了某些特殊图类的彩虹连通数。此后,图的彩虹连通数受到了广泛关注,现在已成为图论研究中的一个热点。2011年,Chakraborty等人证明了计算图的彩虹连通数是一个NP-困难问题。从而确定某些图类的彩虹连通数或建立彩虹连通数好的上下界是非常有意义的。在本文中我们主要开展有限Cayley图的彩虹连通数的研究。  本文总共包括五章。在第1章中,我们给出了论文中需要用到的基本概念,介绍了彩虹连通数的研究背景,并且概述了本文所取得的主要结果。  2011年,李恒哲等人利用极小生成集给出了交换群上Cayley图的彩虹连通数的一个上界。这促使我们研究非交换群上Cayley图的彩虹连通数。在第2章中,我们首先确定了ladder图和M(o)bius ladder图的(强)彩虹连通数,并且回答了一个关于交换群上Cayley图的彩虹连通数与极小生成集关系的公开问题。对于具有一定特殊结构的Cayley图,利用商图技巧,我们给出了界定其彩虹连通数的一种简化方法。该方法被成功地应用于确定或界定二面体群上Cayley图的彩虹连通数。此外,应用此方法,我们还改进并重新证明了李恒哲等人关于交换群上Cayley图的彩虹连通数的结果;刻画了达到上界的极小边数图,这样的图只能是一些圈或K2的Cartesian乘积。  在第3章中,我们把彩虹连通数的概念及前章的简化方法拓展到了强连通有向图。首先利用极小生成集给出了交换群上有向Cayley图的彩虹连通数的一个上界,证明了交换群上有向Caylcy图的彩虹连通数不超过其极小生成集中各元素阶的和。此外,我们研究了一般的不可分强连通有向图的彩虹连通数,证明了此类图的彩虹连通数不超过图的顶点数。  在第4章中,我们提供了一种对具有某种结构特征的图的彩虹2-连通数进行划界的方法。在此方法基础上,我们研究了Cayley图的彩虹2-连通数,特别是定义在交换群和二面体群上的Cayley图。接下来,我们研究了一种特殊图的彩虹2-连通数,并且给此图的彩虹2-连通数一个上界。  在第5章中,我们对具有小彩虹顶点连通数的图Γ进行讨论。首先,我们证明了如果连通图Γ的边数大于等于(n-2/2)+2,那么Γ的彩虹顶点连通数不超过2。其次,我们刻画了具有n个顶点,直径不小于3且团数为n-s的图Γ的彩虹顶点连通数,这里1≤s≤4。最后,我们决定了所有顶点数小于等于8的三度图Γ的彩虹顶点k-连通数,这里1≤k≤3。
其他文献
Kazhdan-Lusztig理论是1979年由D.Kazhdan和G.Lusztig在研究Coxeter群与Hecke代数的表示时创建。它已在表示论、代数几何和组合学等数学分支中得到了广泛的应用。Kazhdan-Lus
学位
该文研究线性奇异时滞系统的控制设计.分析了线性定常奇异时滞系统的稳定性,以及解的估计问题,考虑了线性奇异时滞系统的各种观测器的设计问题,以及基于观测器的反馈镇定控制
本文中,我们利用Moser迭代的技术分别对两类问题进行了讨论.在第三章,我们将给出具有小负曲率的流形上Laplace算子的第一特征值的下界估计;第四章,我们会给出一类完备非紧流
本文主要建立了一类特殊连通单连通黎曼对称空间的分类,讨论了连通单连通的Lorentz对称空间上共轭迹与割迹之间的关系,然后给出了Aloff-Wallach空间上的齐性Randers-Einstein度
整数分拆理论是组合数学中的一个重要研究方向,它在群论、概率论、数理统计及粒子物理等方面都有重要的应用。分拆统计量是分拆理论的一项重要研究课题,特别是统计量“钩”和