图的剖分的强边色数研究

来源 :郑州大学 | 被引量 : 0次 | 上传用户:dengdq123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G =(V,E)的强边着色是将多种颜色分配给图G的边集,使得着每一种颜色的边的集合是图G的一个导出匹配;图G的强边色数指的是在图G的所有强边着色中需要的颜色最少的强边着色的颜色数,记为x’s(G).对图G中的一条边e进行剖分指的是删除边e,添加一个新的顶点x并且将x和e的两个端点连接.图G的k次剖分图,用G(k)表示,指的是将图G的每一条边都恰好进行k次剖分得到的图.设Pm和Pu分别为包含m和n个顶点的路.平面(m,n)-格子图定义为Pm和Pn的乘积图Pm□Pn.我们用Kn表示n个顶点的完全图.本文研究平面格子图Pm□Pn的k次剖分图的强边色数以及完全图Kn的k次剖分图的强边色数.论文的主要结果如下:(1)对于平面格子图G= Pm□Pn,当m = 1或者n = 1时,xs’(G)= e(G)若e(G)<3,x’s(G)= 3 若 e(G)≥ 3;当 m = 2,n = 2 时,x’s(G)= 4;当 m = 2,n ≥ 3 或者m ≥ 3,n = 2 时,x’s(G)= 6;当 m>3,n ≥ 3 时,x’s(G)= 8.(2)令G(kk)是平面格子图G = Pm□Pn的k次剖分图.当m = 1或者n = 1时,x’s(G(k))= e(G)若 e(G)<3,x’s(G(k))= 3 若 e(G)≥3;当 m = 2,n = 2 时,x’s(G(k))= 3若k + 1为3的倍数,x’s(G(k))= 4若k+1不是3的倍数;当m = 2,n ≥ 3或者m ≥ 3,n = 2 时,x’s(G(k))= 4;当 m ≥ 3,n ≥ 3 时,x’s(G(k))= 5.(3)对于完全图H = Kn(n≥ 2),我们有xs’(H)=(2n).(4)对于完全图H=Kn(n ≥2)的k次剖分图H(k).当k=1时,xs’(H(k))=n;当>2时.x’s(H(k))= 3 若 n = 2,xsiH(k))= n 若 n≥ 3.
其他文献
排序问题的大部分文献都假设机器总是一直可用的.然而在实际生产过程中并非如此.本学位论文考虑的是机器并非是一直可用的,即机器具有一个不可用区间.这里的不可用区间分两种
“羌”有广义和狭义之分。羌族是一个古老而伟大的民族,我国现在许多民族都是由古羌民族发展演变而来的,可以说古羌民族是一个“输血民族”。陕西省宁强县自古以来便是氐羌民
随着历史课程改革的不断深化,对历史教科书的研究越来越多,研究角度和内容也较为广泛。如研究一套历史教材编写方式、辅助系统及部分内容,或者对两套教材同一部分内容比较。
伴随互联网和大数据的发展,图像加密方法的研究就成为当前信息安全领域的研究热点之一。数字图像作为当代多媒体中信息的表达形式,传统的图像加密技术难以满足数字图像加密数
数学经验是数学教育中不可忽视的因素。近年来,在新课程标准改革背景下数学经验对于中学教学及学生学习的重要意义备受重视。数学经验在课堂教学中的高效应用离不开科学、高
在恒同机中每台机器都有相同的速度,这里我们假设所有机器的速度为1.这样工件的加工时间与机器没有关系,仅与它自身的长度有关.限选机器是指机器因功能不同导致工件在选择机
视频帧率上变换算法(Frame Rate Up-conversion Algotirhm)作为一种常见的图像后处理算法,旨在通过技术手段将低帧率的视频转换为高帧率的视频,有着广阔的应用的场景。3DRS算
民国时期的职业指导是在世界思潮影响下教育领域的一项重大革新,在输入和传播国外先进理论基础上结合当时现实国情形成了独具特色的思想体系和实践传播系统。职业指导理论从
近年来,随着传感器技术,计算机网络和无线通信的快速发展,无线传感器网络已成为重要的研究对象并被广泛应用于医疗、军事、环境监测等众多领域。在环境监测领域,大规模的无线传感器网络通常被部署于无人监管、气候复杂的野外环境中。在长期使用的过程中,传感器网络中的数据经常遇到漂移、丢失等问题。这对于终端用户来说是一个严重的问题,因为在无线传感器网络的环境监测应用中必须使用精准的数据,才能制定科学决策。本文针对
中国道教艺术传承数千年,影响深远,用于日常供奉和斋祭的神仙画像或雕塑传世众多,其中最著名的便是位于山西芮城的永乐宫三清殿内的《朝元图》壁画。《朝元图》是元代壁画艺