收缩临界5连通图的5度顶点数和平凡不可收缩边数的新的下界

来源 :广西师范大学 | 被引量 : 1次 | 上传用户:wangxiao8910
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果将k连通图G中的一条边收缩之后所得到的图仍然k连通,川称这条边为G的k可收缩边。利用队至少是5的3连通图中存在3可收缩边这一性质,_1980年Thomassen使用归纳法统一证明了关于平面图的Kuratowski等三个重要定理.自那以来,人们对k连通图中k可收缩边进行了大量的研究不存在k可收缩边的完全k连通图称为收缩临界k连通图.由于收缩临界k连通图每一个性质的否定都可得到k连通图中存在k可收缩边的允分条什,因而对k连通图中k可收缩边进行研究就转化为对收缩临界k连通图性质的研究。 最先Egowa证明每一个收缩临界k连通图有一个基数小于等于k/4的断片,由此可推出当k=4,5,6,7时,收缩临界k连通图的最小度等于k.已经知道不存在收缩临界3连通图,收缩临界4连通图的结构已经完全清楚,它们是两炎特殊的4正则力,接着自然要想弄清收缩临界5连通图的结构,经过多年的探索,人们发现这是一个十分困难的问题.为了弄清收缩临界5连通图的结构,首先要了解收缩临界5连通图性质.山前面Egawa的结果知道收缩临界5连通图至少有一个5度顶点,对于收缩临界5连通图中5度顶点的分布,袁旭东在1994年得到: 定理A 收缩临界5连通图中每一个点都与1个5度点相邻。 由此可以推出G中至少有1/5│G│个5度顶点。1997年苏健基进一步证明了: 定理B 收缩临界5连通图中每一个点都与2个5度点相邻。 由此可以推出G中至少有2/5│G│个5度顶点.到了2003午,Ando又重复得到袁在1994年得到的结果.对于收缩临界5连通图G中5度顶点数的下界,最近覃城阜改进到: 定理C 设G是收缩临界5连通图,则G至少有4/9│G│个5度顶点。 本文进一步得到: 定理1 若G为收缩临界5连通图,则G中至少有1/2│G│个5度顶点。 对于收缩临界k连通图G,最早Thomassen证明图中都有三边形,后来Mader改进到有│G│/3个三边形,最近Kriesell证明至少有2│G│/3个三边形山丁收缩临界5连通图中有很多三边形,又有很多5度顶点,因而也会有不少通过5度顶点的三边形.如果k连通图的一条边在三边形上,并且它所对的顶点是k度顶点,也即这条边的两个端点有一个公共邻点是k度点,这条边显然是不可收缩边,称为平凡不可收缩边.Ando研究了收缩临界5连通图中平凡不可收缩边的分布,证明了: 定理D 收缩临界5连通图G至少有1/2│G│条平凡不可收缩边。 他还提出猜想: 猜想收缩临界5连通图G至少有2│G│条平凡不可收缩边。 最近李向军证明了: 定理E 收缩临界5连通图G至少有│G│+1条平凡不可收缩边。 本文在此基础上进一步得到: 定理2 若G为收缩临界5连通图,则G中至少有3/2│G│条平凡不可收缩边。
其他文献
期刊
多右端线性方程组在信息论、控制论和计量经济学等领域有广泛的应用。块GMRES算法是求解非对称多右端线性方程组最有效的迭代算法之一。在执行整体的块GMRES算法时,所需的计算
根据德国经济研究所的一份研究报告,1994年世界15个最大的出口国和地区排名如下(单位:亿美元):1.美国 5127;2.德国 4219;3.日本 3970;4.法国 2360;5.英国 2052;6.意大利 189
本文在已有细分方法的研究基础上,首先提出了一类包含两个形状参数μ,ω的双参数六点细分法,可以用来构造光滑插值曲线和光滑逼近曲线.形状参数μ,ω对细分法的收敛性及连续性有重
中国出口机器走向高端。设在湖南的建筑机械制造商三一集团计划征服世界,当身穿蓝色工作服、头带黄色硬质工作帽的工人在巨型移动式液压起重机和混凝土搅拌车上辛苦工作的时
电磁弹性材料是一种能够实现机械能、电能和磁能相互转化的复合材料,它在新型的智能材料与结构等众多高新技术领域都显示出良好的应用前景。电磁热弹性材料可以实现机械能、电
在课堂教学过程中,教与学的活动是紧扣教学目标而展开的,目标达成度高,才会有好的教学效果。而学习活动又是学生获取知识的主要载体,是学生提高能力的重要路径。因此,在思想
施工现场管理是工程项目管理的关键部分,对搞好工程质量、提高企业效益、降低生产成本、杜绝各类安全事故、提高建筑企业在市场中的竞争力起着重要作用。本文结合自身多年的工
期刊
小学语文教学中的作文教学是语文学习的重要环节,也是能够全面的提高小学生们的语文素养的关键学科,同时小学作文也是教学过程中的重点和难点环节.在新课标的教学改革背景下,
随机化方法已经成为社会敏感性问题调查中的一种重要的方法和常用的手段。继Warner开创随机化调查技术之后,在近四十年的随机化调查技术的理论研究中,国内外的学者研究的是对