图的Z3-连通性及非正常染色的研究

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:yhmlivefor54
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在研究四色猜想时,Tutte引入了整数流的概念,并提出3-流猜想:每个4-边连通图存在处处非零3-流.设D是图G的一个定向.设E+(u)(E-(u))表示在G中以u为起点(终点)的所有边的集合.对任意u∈V(G),若存在一映射f:E(G)→{±1,±2,…,±(k-1)}使得则称图G存在处处非零k-流.群连通这一概念是Jaeger等在1992年作为整数流概念的推广而提出来的.设A是以0为单位元的Abel群.称b(u)为图G的一个A值零和映射如果映射b:V(G)→A都满足∑u∈V(G)b(u)=0.若对任意b,总存在映射f:V(G)→A\{0}使得对任意u∈V(G),满足:则称G是A-连通的.并在文献[25]提出如下猜想:每个5-边连通图都是Z3-连通的.目前,围绕这两个猜想,对满足一定局部条件的图G是否存在处处非零3-流,或图G是否为Z3-连通的等相关方面作了广泛的研究.据此,本文先主要作了以下方面的研究.第二章,Lovasz等[J.Combin.Theory,Ser.B,103(2013)587-598],Lai等[Inform.Process.Lett.,111(2011)1085-1088]以及Ma和Li[Discrete Math.,336(2014)57-68]证明了Jaleger等的Z3-连通猜想归结于5-边连通无爪图的研究.在图G中,若u,v是2-距离的两点,令I(u,v)表示两点u,v公共邻点的集合.即,I(u,v)=N(u)∩N(u).用(?)表示一类简单连通图G的集合使得G∈(?)当且仅当G是无爪图且对于G中任意一对2-距离的顶点u,v满足|(u,v)|≥2.特别地,如果图G没有2-距离的顶点对,我们也视G∈(?).在本章中,我们证明了若G∈F,则G不是Z3-连通的当且仅当G是属于三类较好特征的图之一,或者G是7个特殊的非Z3-连通图之一第三章,设G是阶数为n≥4的2-边连通简单图.对于边e=uv∈E(G),定义dG(e)=dG(u)+dG(v).令F表示所有阶数为n≥4的2-边连通的简单图集合使得G∈F当且仅当对图G中任意一对独立边e,e’满足dG(e)+dG(e’)≥2n.在本章,我们证明了若G∈F,则G不是Z3-连通的当且仅当G是K2,n-2,K2,n-2+,K3,n-3,K3,n-3+中之一或是16个特殊例外图中之一.从而,该结果推广了Zhang等[[55], Degree sum condition for Z3-connectivity in graphs, Discrete math.,310 (2010) 3390-3397]中的结论.本文第四章研究了一类平面图的非正常染色问题.设G是平面图.设d1, d2,,dk是k个非负整数.若能用颜色1,2,,k对图G的点进行染色,使得染颜色i的点集K所诱导的子图G[Vi]的最大度至多为di,i∈{1,2,,k},则称G是(dl,d2,,dk)-可染的.Borodin和Raspaud [[10], A sufficient condition for planar graphs to be 3-colorable, J. Combin. Theory, Ser B,88 (2003),17-27]提出猜想:不含相邻3-圈且不含5-圈的平面图是3-可染的.在本文第四章,我们证明了不含相邻3-圈且不含5-圈的平面图是(1,1,0)-可染的.这一结果进一步地加强了Xu [[50], On (3, 1)*-coloring of planar graphs, SIAM J. Disceret Math.,23 (2009), 205-220]中的结论.
其他文献
结合西安地铁十号线跨渭河大桥主桥承台施工,介绍了厚砂层水中承台锁扣钢管桩围堰施工技术。在透水性饱和砂层中,基于弹性支点法对各施工阶段锁扣钢管桩围堰构件进行设计检算,确保围堰构件刚度满足要求;在钢管桩振沉过程中采用高频液压振动锤振沉施工,解决了在厚砂层地质条件下,锁扣钢管桩因砂土挤密和桩端土塞效应引起的沉桩困难问题,取得良好的沉桩效果;在承台施工完成后设置混凝土圈梁置换围堰底层内支撑圈梁,以满足因施
本论文研究图中结构与相关参数,包括三个方面的内容.二部图的弱偶泛圈性、线性森林的饱和数以及加强超立方体的容错性.图的哈密尔顿性是结构图论的一个重要研究课题.该问题的产生与发展和著名的四色猜想问题的研究密切相关,因而受到国内外许多图论专家和学者的广泛关注.与此相关图的泛圈性、偶泛圈性亦成为结构图论的重要研究课题.1989年,Tian和Zang[Bipancyclism in Hamiltonian
“冷战”结束后的20世纪九十年代初期,法国对非的政策影响力大不如前。但对科摩罗联盟来说,外交政策的影响力却极大地增强。科摩罗群岛自古以来,因其在西印度洋,更确切地说,是其在莫桑比克海峡(世界最重要的航海线路之一)的重要战略地位吸引着大国的注意力。而且,近期科摩罗群岛勘探出石油、天然气和矿物等重要自然资源。本文主要阐述自科摩罗联盟独立以来至2015年间法国对其产生的影响力变迁,旨在通过描述法国政策的
学位
子图存在性问题是图论研究的一个热点,对其进行研究不但有重大的理论意义,而且在理论计算机科学、生命科学、管理科学和信息科学中有很强的应用背景.本论文主要研究图中参数与特定子图存在性之间的关系,全文共分四章,主要’内容如下:在第一章,我们首先给出了文中出现的一些基本概念和符号.接着介绍了本文的研究背景和研究意义,国内外在这方面的研究情况.通过对本文研究背景及研究现状的讨论,说明了本文主要研究工作的必要
海洋聚球藻是单细胞浮游植物,在世界海洋的绝大部分区域都广泛存在。对全球叶绿素生物量和初级生产力具有重要贡献,在海洋生态系统的碳循环及食物链中扮演着举足轻重的角色。各种逆境胁迫,如强光、高/低温、高盐、营养限制等都会引起细胞氧化损伤,而这些逆境在蓝藻的栖息地经常会发生。超氧化物歧化酶(SODs)是有氧环境中有机体减轻氧化胁迫的第一道屏障,根据其螯合的金属离子不同,一般有FeSOD、MnSOD、Cu/
"最是书香能致远。"一个民族的精神发展,很大程度上取决于全民族的阅读水平。只有不断地阅读学习,才能促进人的全面发展,促进社会全面进步,成就美好未来,实现中华民族伟大复兴。一个善于阅读的民族,一定是一个有希望的民族;一个善于阅读的国家,一定能成为一个强大的国家。《义务教育教科书教师教学用书》(道德与法治七年级上册)指出:"‘阅读感悟’属于‘经验扩展型’链接活动设计,为教师教、学生学呈现更为开阔
期刊
本文主要研究了非等熵单极和双极Navier-Stokes-Poisson方程波的稳定性.首先,我们构造光滑逼近稀疏波且稀疏波的波强允许是大的,然后证明了我们所构造的非平凡解的全局存在性且相应的双极非等熵Navier-Stokes-Poisson方程柯西问题的解在小扰动时是时间渐近稳定的.其次,由于在拟中性假设下电势在边界取不同的值,我们构造了粘性接触间断波且证明了单极Navier-Stokes-P
间歇脉冲星的发现对脉冲星自转减慢机制、磁层结构以及辐射机制等问题的研究带来了相当的机遇和挑战。本文主要从间歇脉冲星的辐射特点和自转减慢特征出发,研究它的开状态(即可以观测射电辐射)和关状态(即观测不到辐射)的制动指数,以及这两个状态之间的互换特征。下面简单地介绍主要研究工作。在脉冲星星风制动模型的基础上,第二章给出了一个简单而有用的预测间歇脉冲星制动指数的方法。制动指数的研究对了解脉冲星转动能损耗
The groups that consist of non-bijective transformations on a non-empty set A where the binary operation on a group G is the composition of transformations have been recently given. A permutation grou
学位