论文部分内容阅读
图论作为离散数学的一个重要分支,它在化学,生物信息学和社会科学等方面都有着十分广泛的应用.图的连通性理论是图论研究中比较基础但又极具意义的内容,连通图的构造就是要研究的课题之一,它与网络模型和组合优化联系密切,使它具有重要的理论价值和应用价值.自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中的条件是不可缺少的.