图的消圈数与不可分独立数

发布时间：2020-11-21 07:36

　　图的消圈数和不可分独立数是图划分理论的两类经典问题,两者之间有着千丝万缕的联系.它们在无线传感器网络和组合电路设计等领域中有着广泛的应用,近些年来受到了极大关注.本文主要研究图的消圈数和不可分独立数及其应用.具体内容如下:1.首先对图论的一些基本概念和术语做了介绍.随后,比较全面地列举了与本文相关的消圈数和不可分独立数问题的研究背景、发展现状.最后给出了本文的主要结论.2.首先运用图嵌入的方法给出了一个计算次3-正则图的消圈数的公式.进一步,给出了在3-正则图中(?)成立的充分必要条件.3.借助消圈数这一参量分别建立了满足条件(?)的图是Hamilton图、泛圈图和边-Hamilton图的充分条件.4.首先给出一个计算图的不可分独立数的公式,然后借助这个公式求得了超立方体(?)的不可分独立数.随后,利用两个圈的笛卡尔积(?)的消圈数,给出了(?)的不可分独立数.与此同时,找到了(?)的最大不可分独立集.最后,刻画了次3-正则图的最大不可分独立集的分布,并对图的最大亏格和不可分独立数这两者的关系做了进一步讨论.5.首先借助最大割给出了计算图二部顶点挫败指标的具体公式,然后利用此公式得到了一些图类(包括稠密图)的二部顶点挫败指标的上界或者精确值.同时,我们研究了五类组合图的二部顶点挫败指标.最后,对稠密图的消圈数问题进行了探讨.
【学位单位】：华东师范大学
【学位级别】：博士
【学位年份】：2020
【中图分类】：O157.5
【部分图文】：

情形,森林,正则图,三角形

第二章图的消圈数与连通消圈数假设是这个点且()={,},易证=+连通且无三角形.若()≤2,通过归纳假设,它有一个森林满足||≥12(1)929≥()1.否则,是3-正则图.而Bondy等人[12]证明了对任一个无三角形的次3-正则图,()≥2|()|313.从而有一个森林满足||≥23(1)13≥()1.在以上任何一种情形中,均有∪{}是中阶数≥()的森林.断言5.若有一个2-度点,则()≥().假设是个2-度点且()={,}.由断言4可知和还有另外一个共同的邻居,记为.结合断言1,2,3,我们可以推导出()=()=()=3.接下来,分如下两种情况来讨论情况1.顶点和有除和外的第三个共同邻居,记为.在这种情形下,由断言3,()=3.假设和有除和以外的第三个共同邻居,记为.若()=2,那么是由{,,,,,}作为顶点集构成的边数为8的次3-正则图,并且={,,,}诱导出的一个森林(见图2.2.3).不难验证||≥62×8929.若()=3,则与的某条割边关联,这与是2-连通这一假设矛盾.所以,顶点对与只有两个共同的邻居,那就是和.这样,={,,}+连通且无三角形,从而它有森林满足||≥32(5)929≥()2.因此,∪{,}是的一个诱导森林且||≥().图2.2.3:()=2的情形.情况2.顶点和只有两个共同的邻居和.令和分别是和的第三个邻居.从断言3可知()=()=3.假设/∈(),={,,}++.显然,连通且无三角形.由归纳假设,有一个森林满足||≥32(5)923≥()2.从而∪{,}是的一个森林·19·

平面图,方法,Halin图,广义

第二章图的消圈数与连通消圈数图2.3.1展示了当()的一个分支分别是4-圈,5-圈,4-路和5-路时,1,2,1的选取方式.图2.3.1:的选取方法.接下来,我们利用定理2.10来证明()=()在3-正则Halin图和广义Petersen图中均成立.Halin图是由德国数学家Halin提出的极小3-连通平面图.给定一棵树,其内部顶点度数至少为3.将嵌入到一个平面中,然后添加一些依次连接的叶子的边来组成一个圈.由此得到的图=∪即为Halin图,其中称为的特征树,为的伴随圈.我们把定理2.10应用到3-正则Halin图上,很容易得到()=().这是因为选取作为的一棵Xuong-树后,()的唯一可能的奇连通分支至少包含3条边.广义Petersen图,是由顶点集(,)={,:1≤≤}和边集(,)={,+1,+:1≤≤}构成的阶数为2的图,其中,正整数且>2.这里所有的下标均取模.令是和的最大公约数.为方便起见,记={:1≤≤},={:1≤≤}.Gao等人在文献[33]中刻画了广义Petersen图的内部结构.引理2.3(Gao等[33])[]是由长度为的个圈组成,且每个圈均可表示为如下形式=++2···+(1),下标取模,=1,2,...,.·21·

图的消圈数与不可分独立数