【摘 要】
：
近些年,图的连通染色得到了蓬勃的发展。图的连通染色是研究在边染色情况下图的连通性问题,例如:彩虹连通染色,正常连通染色,单色连通染色和无冲突染色。我们知道,研究一个图的边连通性有两种方式,一种是通过路来研究,而另外一种是通过边割研究。上述四类连通染色均是通过路来研究边染色图的边连通性。Chartrand等人于2018年提出了彩虹不连通染色的概念,彩虹不连通染色是通过彩虹边割来研究一个图的彩虹连通性
论文部分内容阅读
近些年,图的连通染色得到了蓬勃的发展。图的连通染色是研究在边染色情况下图的连通性问题,例如:彩虹连通染色,正常连通染色,单色连通染色和无冲突染色。我们知道,研究一个图的边连通性有两种方式,一种是通过路来研究,而另外一种是通过边割研究。上述四类连通染色均是通过路来研究边染色图的边连通性。Chartrand等人于2018年提出了彩虹不连通染色的概念,彩虹不连通染色是通过彩虹边割来研究一个图的彩虹连通性问题。本文研究图的单色连通性问题,主要内容分为两部分:第一部分（第二章和第三章）是关于图单色连通染色的推广及其研究,第二部分（第四章到第七章）是关于图单色不连通染色问题的研究。事实上,在这两个部分中,我们分别通过单色路和单色边割来研究图的单色连通性问题。对一个边染色图,如果一条路（一个边割）中的边染相同颜色,那么称该路为单色路（该边割为单色边割）。Caro等人提出了单色连通染色的概念,它要求在一个边染色图中,任何两个点由一条单色路连接。在本文中,我们首先从三个方向推广了单色连通染色的概念,推广如下:对一个边染色图G,如果任何两个点之间有k条边不交的单色路,那么称该边染色为G的单色k-边连通染色（或简称MCk-染色）;如果任何两个点之间有k条边不交的单色路且这些路的颜色互不相同,那么称该边染色为G的彩虹单色k-边连通染色（或简称RMCk-染色）;如果任何两个点之间有k条边不交的单色路且这些路的颜色相同,那么称该边染色为G的一致单色k-边连通染色（或简称UMCk-染色）。图G的MCk-数（RMCk-数,UMCk-数）为能保证G存在MCk-染色（RMCk-染色,UMCk-染色）的最大颜色数,记作mck（G）（rmck（G）,umck（G））。其次,我们讨论图的单色不连通染色。如果一个边染色图G的任何两个点被一个单色边割分开（删除这个单色边割后,这两个点在不同的连通分支中）,那么称该边染色为G的单色不连通染色（或简称MD-染色）,并称能保证G存在MD-染色的最多颜色数为G的MD-数,记作md（G）。在第一章,我们引入了与本文相关的概念和符号,介绍了前人做的一些结果,并列举了本文的主要结论。在第二章,我们研究图的单色k-边连通染色和一致单色k-边连通染色。首先,我们提出了关于图的单色k-边连通染色的一个猜想,并验证了该猜想在k=2的情况下以及一些特殊图上是成立的;其次,我们研究了图的UMCk-数和它的最小k-边连通支撑子图之间的关系在第三章,我们研究图的彩虹单色k-边连通染色。首先,我们给出了一个图存在彩虹单色k-边连通染色的充分必要条件;其次,我们给出了RMCk-数达到下界的一些条件;最后,我们研究了RMCk-数的锐阈函数。在第四章,我们介绍了研究图单色不连通染色所用到的一些结论,这些结论对后续证明有很大帮助。此外,我们给出了 MD-数为1的一些图类,并证明了几乎所有图的MD-数为1。在第五章,我们研究了四类乘积图（笛卡尔积图,强积图,字典积图以及张量积图）和线图的MD-染色问题。在第六章,我们研究了关于单色不连通染色的两类极值问题:Nordhaus-Gaddum类型问题和Erdos-Gallai类型问题。在第七章,我们提出了关于MD-染色的一个猜想:k-连通图G的MD-数小于等于[|G|/k]。我们验证了当k=1,2以及k≥[|G|/2]时该猜想成立。我们也研究了直径为2的图,并刻画了 k=2以及k≥[|G|/2]时的k-连通极图。此外,我们给出了关于MD-数的两个上界,其中一个和连通度有关,而另一个和独立数有关。在第八章,我们提出了有待进一步研究的问题。
其他文献
1994年,编码学者发现一些重要的非线性二元码可以由Z4上一些特殊的具有好的结构的线性码通过Gray映射构造.在此之后,编码学者开始研究有限环上的纠错码理论.本文在已有研究成果基础上,发展有限环和有限域上的纠错码理论,研究有限环上线性码的覆盖半径,有限环上斜常循环码和斜循环码的代数结构以及有限域上优化码的构造,获得有限域上具有较好参数的线性码并将其应用于构造新的量子纠错码.具体内容如下:第一章,介
本学位论文在有理同伦论中,对映射空间,分类空间和本征形式空间进行了研究.本学位论文主要结果如下.（一）本文证明映射空间map（X,Y）的有理同伦型只依赖于X的上同调代数和Y的有理同伦型,其中X是有限的CW-复形,Y是有限型的有理的CW-复形且其极小Sullivan模型形如（Λ（P⊕Q）,d P=0,d Q（?）ΛP）.证明的主要方法是对map（X,Y）的L∞-代数模型应用同伦变换定理.利用上述结果
作为一种研究各类复杂过程和系统的工具,试验设计广泛应用于科学研究、工业、农业、医学等多个领域。试验设计可以分为单次设计和序贯设计。单次设计是一次性完成固定次数的试验,而序贯设计逐次地序贯添加设计点直到达到试验目标。作为一种经济有效的方法,序贯设计既可以避免盲目加大试验样本个数而造成浪费,又不至于因试验样本个数太少而无法得到结论。随着计算机技术的飞速发展,现有的序贯设计已经无法满足各类具有复杂结构试
在[]中,R.Kato和K.Shimomura使用第三个Morava稳定子代数的上同调检测球面稳定同伦群中希腊字母元素的非平凡乘积.本文我们使用他们的方法发现了球面稳定同伦环中希腊字母元素新的乘积:令p ≥ 7,有0≠ξnγsβ1∈π*S,如果n三2 mod 3,s（?）0,±1 mod p.并且写出球面稳定同伦环中α-族,β-族,γ-族,以及R.Cohen元素ξn的乘积中所有能被上同调H*S（3
同时定位与建图（Simultaneous Localization and Mapping,SLAM）是通过对传感器信息的处理,在未知环境中对移动机器人进行定位,并建立环境地图的过程。近年来,随着移动机器人在家庭服务、自动驾驶等领域的应用,SLAM技术也随之得到广泛的研究和发展。基于环境特征的机器人位姿求解与环境建模,是SLAM技术的主要实现途径。面向复杂多样的作业场景,不同种类的特征有着各自的优
本论文主要研究点拟本原边传递图的自同构群和边本原图的分类问题。图的对称性（比如边传递性、弧传递性等）和自同构群是代数图论中的重要研究对象,在其研究过程中群的理论和方法发挥了不可替代的作用。特别是针对具有一定传递性质的图类,许多问题被归约到了拟本原甚至是几乎单的情形。这是本文所进行研究的主要动机。本文的第一项主要工作是关于点拟本原边传递图的研究。设Γ是连通的2倍素数度的G-边传递图,其中G是Γ自同构
本文研究了几类结构张量的理论性质及其张量互补问题,主要讨论了非负Q-张量的张量互补问题解集的具体上下界;Cauchy-Hankel张量特征值的上界;矩形Z-张量、矩形P-张量的性质及相应互补问题解的存在情况。并运用相关算法来计算张量的特征值。论文结构如下:首先,对由张量互补问题可解性定义的Q-张量给出一些新的结果。对于这类结构张量,我们给出了充分条件来保证其相应的张量互补性问题的非零解至少包含两个
随着很多实际问题可以转化为图论问题,图染色发挥越来越重要的作用。作为图连通染色的割版本问题,Chartrand等人在2018年提出了图的彩虹不连通染色。基于图的彩虹顶点连通染色和彩虹不连通染色,同时,为解决频率分配,货物拦截中的相关问题,Bai等人提出了图的彩虹顶点不连通染色。本文主要研究了图的彩虹顶点不连通染色。令G是一个非平凡连通的顶点染色图。对于图G的顶点子集X,如果X中的任意两个顶点有不同
在本文中,我们引入实拟全纯曲线的模空间并研究了它的性质。我们计算了实拟全纯曲线的模空间维数,同时建立了一些3维情形的重要不等式。最后,我们给出我们结果在将来的可能应用。在第一章和第二章,我们首先给出我们主要结果的介绍和确立我们的惯例与符号。第三章,我们给出实拟全纯曲线的模空间完整的定义,并且计算了实拟全纯曲线的模空间在给定边值条件下的实质维数。主要结果的证明由一系列的引理组成,我们使用了裤子归纳法
本博士论文主要研究组合数论中的几个重要问题:关于不变量disc（G）的确定和反问题,关于不变量skexp（G）（G）的确定和反问题,某些二项式系数的最大公因子问题以及最小公倍数倒数和的上界估计问题。设G为有限（加法）交换群,我们用disc（G）表示最小的正整数t,使得群G上的任何一个长度大于等于t的序列S都有两个不同长度的非空零和子序列。在第二章中,我们就一些新的群G,确定了 disc（G）的值。