论文部分内容阅读
边染色图的连通性问题近十年来十分活跃,其中最早出现的图的彩虹连通数在网络理论中具有重要的应用,引起了学者对于边染色图的连通性问题的广泛关注和兴趣.与图的彩虹连通数相对的一个参数是图的单色连通数mc(G),表示使得图G中的任意两个点之间都有一条单色路的最大边染色数.它最早是由Caro等人在2011年提出的.现有的研究刻画了图的单色连通数与图的一些参数(如边,点,色数等)存在的若干联系.Caro等人根据图的参数给出了单色连通数的上下界并且确定了一些特殊图类(如K3-free,直径至少为3,完全r部图等)的单色连通数.对于直径为2的图的单色连通性研究,迄今进展仍然很缓慢.经过数年的发展,研究者们对图的单色连通数及其相关参数进行了探索并且取得了积极的进展. 本论文主要研究各种特殊图类的单色连通数.本论文的主要结构和研究内容分为以下四个部分. 第一章主要介绍了本论文所涉及的基本概念,阐述了图的单色连通性问题的发展和研究现状,以及简要地列举了本文的主要研究结果.第二章研究了有关三角形条件下图的单色连通数,给出了相关图的单色连通数的值.第三章研究了两个不相交图的联图的单色连通数,给出了联图的单色连通数的表达公式.第四章研究了单色连通数的一个推广问题,也即树的多色连通数的表达公式。