3-连通图中圈外的可去边的分布情况

来源 :山东大学 | 被引量 : 0次 | 上传用户:liongliong593
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论作为离散数学的一个重要分支,它在化学,生物信息学和社会科学等方面都有着十分广泛的应用.图的连通性理论是图论研究中比较基础但又极具意义的内容,连通图的构造就是要研究的课题之一,它与网络模型和组合优化联系密切,使它具有重要的理论价值和应用价值.自1961年,Tutte[33]利用3-连通图中可收缩边和可去边的存在性给出了连通图的构造方法之后,人们便致力于研究各种类型的连通图的构造.事实上,可收缩边和可去边这两种运算不仅在连通图的构造上发挥着重要的作用,它们还是递归证明图的某些性质的重要工具,这类问题获得了数学家Thomassen等人的关注和研究.对于3-连通图中的可去边,Holton等[14]首先给出了连通图中可去边的定义.早在1969年,类似于3-连通图中的可收缩边的结果,Barnette等[5]证明了每个阶大于4的3-连通图必有可去边,并且给出了 3-连通图的一个递归构造方法.后来尹建华[39]定义了 4-连通图中可去边的概念,并证明了 4-连通图G中不存在可去边的充要条件是G是阶数为5或6的二循环图,利用这个结果和4-连通图中可收缩边的性质给出4-连通图的一个递归构造方法,他的方法比Slater[26]的构造方法简单很多.2005年,徐丽琼[37]在她的博士毕业论文中把3-连通图和4-连通图中可去边的概念推广到了k-连通图,并证明了不同构于K6的5-连通图中必有可去边.更重要的是,她还对不含可去边的k-连通图作了如下猜想:对于k(k≥ 3)连通图G,G中不存在可去边当且仅当k为奇数时,G同构于Kk+1;当k为偶数时,G同构于Kk+1或H(k+2)/2·后来苏健基等[30]人证实了这个猜想.至此k-连通图中可去边的存在性问题得到了圆满解决.与此同时,连通图中可去边的分布情况也被广泛研究.但目前的研究主要集中在一些特殊的子图上,这里的特殊子图主要指某些特定的圈和生成树.哈密顿圈历来是图论研究的热点问题之一,数学家Thomassen就曾关于哈密顿图提出了一个经典的问题[32]:最小度至少为3的哈密顿图G中是否存在一条边e,使得G-e和G/e仍是哈密顿的.通过分析发现,如果e是哈密顿圈上的一条边,则G/e仍是哈密顿的,但是G-e会破坏包含边e的哈密顿圈.但如果e是哈密尔顿圈外的一条边,则G-e并不会破坏不包含边e的哈密顿圈.鉴于此发现,探究3-连通图中可去边在圈外的分布情况就很有必要.受Thomassen问题的启发,本论文通过应用分离组和极大扇等工具,首次研究了 3-连通图中圈外的可去边的分布情况.当然,这里对3-连通图G是有要求的,我们重点考虑了当G不含扇作为子图和仅含一个扇作为子图时的情况,得出以下结论.除此之外,本文还构造一个含两个扇作为子图的3-连通图G,并使得圈C外无可去边,从而说明定理2中的条件是不可缺少的.本文的主要结果如下.定理1.设G是阶至少为6的3-连通图,C是G中的一个圈.若G不含扇作为子图,则任意圈C外至少有两条可去边..定理2.设G是阶至少为6的3-连通图,C是G中的一个圈.若G仅含一个扇作为子图,则任意圈C外至少有一条可去边.定理3.设G是阶至少为6的3-连通图,C是G中的一个圈.若G含两个扇作为子图,则可以构造一个3-连通图G,使得圈C外无可去边,从而说明定理2中的条件是不可缺少的.
其他文献
学位
学位
学位
“提调”在白族村落中是指在家庭或村落仪式中“主事”的人,承担“主持仪式”“总管”“总领”“总理”“领事”“管事”“督管”等工作,促进该项事务顺利进行,是白族村落互助圈、人情圈和社会圈的主要角色。“提调”作为村落文化的主要阐释者,相关的研究在学术界也已取得丰硕的成果。现有关于“提调”文化意义的研究略显单薄,研究范围局限于“提调”的职能职责和称谓,存在重叙述、轻总结,重个案、轻整体的倾向,缺乏理论深度
学位
学位
学位
多孔材料由于其高的比表面积、稳定的化学性质等优点已被广泛应用于气体分离、能量存储、催化反应等领域。多孔材料的种类繁多,包括分子筛、沸石、金属有机框架材料(Metal Organic Frameworks,MOFs)、共价有机框架材料(Covalent Organic Frameworks,COFs)等。其中,COFs 具有化学稳定性高、密度低,并且可以通过引入功能基团满足各种实际应用需求等优点,已
学位
学位