论文部分内容阅读
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。