图厚度Gross-Harary问题的研究

来源 :湖南大学 | 被引量 : 0次 | 上传用户:zhhy0822
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的厚度t(G),简单来说就是将图G分解成若干个平面子图的并的最少平面子图的数目.一般而言,确定图的厚度是一个NP-难问题,因此确定给定图的厚度的值是一项非常困难的工作.并且相对于其他图的拓扑参数,图的厚度的结果较少.对于完全二部图 m,nK的厚度, Beineke, Harary和Moon于1964年给出了如下计算公式(此处公式省略)  仅当m和n同时为奇数且存在整数 k使得n=[2k(m-2/(m-2k))不成立.  依据上述公式,完全二部图的厚度并未全部确定.著名图论学者 J.L. Gross和F. Harary在1980年《拓扑图论的一些问题》的综述论文中提出如下问题:对任意整数m, n,确定完全二部图 m,nK的厚度.本文试图对该问题进行研究,另外我们也对完全三部图的厚度进行了讨论.  第一章主要介绍图的厚度的起源,国内外的研究现状以及本文所需的一些基础知识,同时还简要的介绍了本文的基本结构.  第二章介绍了关于完全二部图厚度的Beineke-Harary-Moon定理的证明.  第三章给出了完全二部图Kn,n+4和Kn,n+8的分解,并确定了其厚度.  第四章对完全三部图的厚度进行了研究,确定了部分完全三部图的厚度.
其他文献
本文主要研究了具有相互干扰和B-D型功能反应函数的捕食模型,全文分为三章。   第一章,绪论,我们来介绍本文的研究背景,主要工作以及预备知识。   第二章,主要研究了具有相
学位