收缩临界6连通图中6度顶点数新的下界

来源 :广西师范大学 | 被引量 : 1次 | 上传用户:googto0726
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
对于F∈V(G),记NG(F)=(U∞FNG(x))-F设G是非完全图,T是最小点割,F是G-T的至少一个分支但不是所有分支的并,则称F是G的断片或T-断片。F=G-T-F,那么F也是T-断片。这时我们称F,F是T分离G所得的两个断片,若F是断片,但F的任何真子集都不是G的断片,则称F为G的端片阶最小的断片,称为原子。为方便起见,我们常常将V(F)与F等同起来。X∈V(G),G中与x关联的所有边的集合记为E(x)设F是图G一个断片,x ∈V(G),如果N(F)包含E(x)中某一条边的2个端点,则称F是一个E(x)断片。 如果将k连通图G中的一条边e收缩之后所得到的图是一个k连通图,那么这条边e就叫做G的k可收缩边,简称可收缩边1961年Tutte证明了阶至少是5的3连通图有可收缩边([15])之后人们对3连通图中的可收缩边进行了广泛的研究,在3连通图中可收缩边的分布和可收缩边条数的下界等方面都得到了计多结果([4])对于k≥4,Thomassen[14]证明了存在无限多个k连通k正则图,这一类图中不含有k可收缩边一个k连通非完全图G若不含有k可收缩边,那么G叫做收缩临界k连通图。为得到k连通图中存在可收缩边的条件,很自然要对收缩临界k连通图(K≥4)进行研究。对于k=4,Martinov[12]清楚地刻画了收缩临界4连通图,即:收缩临界4连通图只有两类:一类是圈的平方,另一类是图4连通3正则图的线图。 当k≥5时,收缩临界k连通图的刻画要困难得多一般地,Egawa[5]证明了每个收缩临界k连通图(K≥4)都存在一个阶至多是K/4的断片,由此我们知道每个收缩临界k连通图中都有一个度至多是[5K/4]-1的点。因此,对于5≤k≤7,每个收缩临界k连通图都有一个k度点,近午来人们围绕收缩临界k连通图中k度顶点的分布以及该类图中k度顶点数的下界做了大量的工作[2]。 用Vk(G)表示图G中k度点的集合,Ando等人提出如下问题: 问题:设k是一个整数且5≤k≤7,对收缩临界k连通图,是否存在一个常数ck,使得|Vk|≥ck|V(G)|.若有,试确定CK的最大值? 对于收缩临界5连通图,袁旭东在1994年得到:收缩临界5连通图中每一个点都与1个5度点相邻,由此可以推出G中至少有1/5|G|个5度顶点1997年苏健基进一步证叫了:收缩临界5连通图中每一个点都与2个5度点相邻。由此可以推出G中至少有2/5|G|个5度顶点到了2003年,Ando双重复得到袁在1994午得到的结果最近覃城早把以上结果改进到:设G是收缩临界5连通图,则|V5(G)|≥4/9|G|。 对于k=6,袁旭东和苏健基在[20]中证明了下面的结果: 定理A 每个收缩临界6连通图都有两个相邻的6度点。 齐恩凤,袁旭东对这一结果做了如下改进: 定理B 设x是收缩临界6连通图中的一个6度顶点,则或者它与一个6度顶点相邻,或者在它的邻域中存在一点y,在y的邻域中有两个相邻的6度顶点。 对于收缩临界6连通图,Ando等人证明了以下性质: 定理C 设G是收缩临界6连通图,H=G[V6(G)].则对任一x ∈W,都存在一个E(x)-断片A,使得(1)H[N(A)∩V6(G)]()2K2或(2)W(G)∩N(A)={x),H[N(A)∩V6(G)]()2K2∪K1 利用定理C,Ando等人得到了: 定理D 收缩临界6连通图G中至少有|G|7个6度顶点。 2005年,赵巧凤和覃城阜等人将这一结果改进为: 定理E 收缩临界6连通图G中至少有|G|/5个6度点。 本文进一步对定理E做了改进,得到: 定理1 收缩临界6连通力G中至少有|G|/4个6度顶点。
其他文献
现代信息技术进入教学领域后,教师从“主讲者”转变为学生学习活动的设计和辅导者;多媒体的介入,使得美术教学上一些难懂、深奥、抽象的知识点变得直观化、形象化、具体化,活
孤子理论的研究在流体力学、量子力学、生物学、海洋工程等诸多领域发挥着日趋重要的应用价值,因此孤子方程的求解在理论和实际上都是十分重要的研究课题。由于孤子方程自身的
作为建筑工程中的一项关键工艺,后浇带的设置能够平衡和释放大部分的混凝土约束应力,因此对实现建筑物连续、无缝的整体结构具有重大意义。本文从后浇带施工在建筑工程中的现实
本文研究求解大型线性方程组Galerkin类方法的收敛性质,包括:重新开始FOM算法的补足收敛性质及其应用;预处理CG算法的误差递减性质。 由于执行整体FOM算法的计算成本会随着迭
算子代数分为自伴算子代数和非自伴算子代数两大类。相对于自伴算子代数,非自伴算子代数更年轻,数学现象更丰富,是一个非常活跃的研究领域。套代数是上三角矩阵代数在无穷维空间
透水事故是矿井五大灾害之一,矿井一旦发生透水事故,轻则恶化生产环境,破坏正常生产秩序,造成工作面接续紧张,重则造成国家资源和财产的损失,造成伤亡或淹井。赵各庄矿西翼急倾斜区
Bott函数(又称广义Morse函数)是Morse函数的推广。Morse理论揭示流形的拓扑性质与Bott函数的临界点之间的联系。 对于一个Hamilton系统,其相轨线位于该系统的等能面(即系统的
本文主要提出两个基于变点模型的控制图分别用来监控参数已知和参数未知的线性模型。同时,我们还研究了由Kim et al.(2003)提出来的三个EwMA联合的控制图的参数估计问题。首先,
本文针对微分方程稳定性理论的几个问题,利用微分不等式、积分不等式、微积分中值定理、Liapunov直接法和V函数构造法研究了两个非自治系统零解关于全部变元的稳定性、部分变
本文对与4-瓦片算子相伴的4-线性形式的有界性和一类恒等逼近进行了研究。文章分为独立的两个部分: 第一部分:本文主要研究了与4-瓦片算子相伴的4-线性形式A,证明了下面的估