图的线性点荫度及相关问题研究

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:pj00000pj
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G是一个有限简单平面图.用V(G),E(G)和F(G)分别表示图G的顶点集,边集和面集,简记为V,E和F.用g(G)表示图G的围长,即G中的最短圈的长度.图G的点荫度是指G的顶点集V(G)的最小划分数,使得每个点划分集的导出子图是一个森林.图G的线性点荫度是指G的顶点集V(G)的最小划分数,使得每个点划分集的导出子图是一个线性森林.设G1,...,Gn为n个图类,图G的(G1,...,Gn)-划分是指将V(G)划分为n个集合V1,...,Vn使得对任意1≤i≤n,都有G[Vi]属于图类Gi.为了方便起见,我们用F,L,△d,Fd和F2分别表示森林,独立集,最大度为d的图,最大度为d的森林和线性森林.在顶点划分的意义下,点荫度可定义为图G有(F,...,F)-划分的最小划分数;线性点荫度则指图G有(F2,...,F2)-划分的最小划分数.图的点荫度最早是由Chartrand,Kronk和Wall在1968年提出的,并且他们证明了平面图的点荫度至多为3.1979年,Garey和Johnson证明了确定任意图的点荫度是NP-困难的.随后,有学者在此基础上提出了线性点荫度的概念.1990年,Poh证明了平面图的线性点荫度至多为3.因此,人们开始考虑使得平面图的线性点荫度为2的充分条件.2006年,Chappell等人证明了 g(G)≥ 6的平面图的线性点荫度为2.同时,他们构造了反例说明存在g(G)=4且vla(G)=3的平面图.因此,我们考虑g(G)=5的平面图是否满足vla(G)≤2,即是否存在(F2,F2)-划分.论文框架结构及内容如下:在第一章中,我们首先给出本文需要的一些基本概念,再简述相关领域的研究现状以及本文的研究成果.1998年,吴建良证明了对Halin图G有vla(G)≤2.在第二章中,我们改进了这个结果,证明了如下结果:(1)若G为Halin图,则vla(G)≤ 2,且每个点划分集的导出子图的每个连通分支的路长l≤max{[△-2/2],3}.在第三章,第四章和第五章中,我们主要使用反证法,通过构造极小反例,探究其结构性质并运用权转移方法,分别证明了以下三个结果:(2)围长g(G)≥ 5且不含相交5-圈的平面图有(F2,F5)-划分.(3)围长g(G)≥ 5且5-圈不与(--圈相邻的平面图有(F2,F4)-划分.(4)围长g(G)≥ 5且不含相邻5-圈的平面图有(F3,F3)-划分.
其他文献
在真核生物中自噬是一种高度保守的分解代谢过程,通过溶酶体与自噬体相融合从而降解多余的细胞成分或有害物质,用以维持细胞生理稳态和响应饥饿或其他恶劣环境。自噬可以分为
相对于目前所使用的由多种半导体手性碳管组成的单壁碳纳米管材料(如用共轭化合物从电弧放电方法制备的碳纳米管中分离的半导体碳纳米管)而言,单手性(9,8)单壁纳米管具有确定的带隙、较合适的管径(即较合适的带隙),由(9,8)碳纳米管制作的晶体管有望在器件开关比和性能的一致性等方面表现出更加优越的性能(如开关比更高、器件的一致性更好等),加上这类器件的电流开关比不会随着VDS的增加而显著降低,因此开展单
学位
帮助企业打破市场同质化现象,运用产品结构与造型基本理论知识,基于产品的使用方式,以用户需求为切入点,对净烟器进行产品改良设计,优化产品结构,增加产品趣味性。依据人体手部尺寸,立足产品使用环境,对产品进行人机分析。通过对产品内部结构进行拆解、梳理,提取产品核心技术部件,分析各个零部件功能,简化功能重复零部件,合并功能重合零部件,构建产品可通用零部件。分析净烟器造型特征,明确净烟器产品族遗传基因结构组
学位
供应链中存在的假冒伪劣现象严重影响了商品的流通,对生产者以及消费者都造成了巨大的损失,甚至会威胁到消费者的生命财产安全。基于RFID技术的供应链防伪系统首先应该建立在
聚合物基复合材料因抗疲劳、抗振性、模量、强度等性能优异,被应用到生活中的各个领域中,比如家庭常用品、航空工业特殊部件(飞机机翼、涡轮叶片等)、汽车、生物医学、环境等。增强颗粒填料推动了聚合物基复合材料应用和发展,被应用到热塑性聚合物和弹性材料领域中,改善材料力学性能。聚合物基复合材料虽然可以直接加工成零部件形状,但是有些特殊零部件需要后续加工才能得到理想形状,加之人们对特殊功能的需求日益增多,这对
学位
本文构造了具有微观经济主体基础的开放经济条件下的DSGE模型,在这一模型中,文中本国是指出口商品到国外的中国,外国指代的是包括美国在内的世界其他主要经济体,模型包含本国
互联网时代的背景下,随着国家对“互联网+政府服务”工作的大力推进,越来越多的政府服务纳入互联网工作中来。在税收领域,税务的征收管理从“征、管、查”三分离的税收征管模
与传统的夹芯结构相比,碳纤维复合材料夹芯结构在特定的力学性能和潜在的多功能集成方面表现出明显的优势,被广泛应用于航空航天和舰船装备等高能耗装备领域。3D-Kagome芯体作为点阵夹芯结构典型构型之一,被认为是一种具有相对最优理论性能的点阵芯体。本文采用榫卯连接工艺制备出全碳纤维复合材料Kagome夹芯结构,并对其准静态压缩和低速冲击性能进行试验与仿真研究。由于芯体交结连接的限制,Kagome复合材
学位
语文学科承载着丰富的内容,语文教育承担着“立德树人”“育人成才”“以文化人”的重要使命,因此,语文教学对语文教师来说具有极强的挑战性。钱梦龙与蔡澄清的教学主要以启发的方式培养学生的自学能力,为教师如何提高自身素养、提升教学能力、承担教学重任、获得专业成长等方面提供了宝贵的经验。作为“导读派”的代表,钱梦龙和蔡澄清经过漫长的实践探索,提出了“三主三式”语文导读法与“点拨教学法”。他们的教学方法都以“
学位
学位