论文部分内容阅读
图G中欧拉迹,是G中的一条取G中所有边的迹。存在欧拉闭迹的图称为欧拉图。如果一个图含有生成欧拉子图,则称这个图具有超欧拉性。
有两个关于这方面的猜想:一个是1995年Chen和Lai[4]提出每个3-边连通,基本5-边连通的图都含有生成欧拉子图;另一个是Lai[6]提出G为3-边连通,基本4-边连通的图。若σ(G)≥7,则该图具有超欧拉性。本文首先证明,若图G最小度δ≥3且σ(G)≥8,则∣E(G)∣≥2∣V(G)∣。然后证明出:G为3-边连通,基本5-边连通的图。若σ(G)≥8,则该图具有超欧拉性。
下面简略诉述证明的思路过程。第一部分:通过Yang[11]的定理,分析得到在δ≥3和σ(G)≥8前提下,只要能保证3度点至少与6点以上的点关联,就可得到∣E(G)∣≥2∣V(G)∣。也就是在保证∣E(G)∣与∣V(G)∣维持一定平衡(满足∣E(G)∣≥2∣V(G)∣等量关系)的同时,去掉与3度点关联的5度点,使得3度点至少与6度点以上的点关联且其他点的度没有改变,至关重要的是3度点的个前后不能改变。反过来思考,5度点至多与五个3相关联,因而可分五种情况讨论。第二部分:通过Nash-Williams∣8∣和Tutte[10]的定理知,要证明图具有超欧拉性,只需要证明∣S∣≥2(w(G-S)-1)=2(w-1)成立。对G-S的连通分支进行特殊的分类,再在图G中将这些连通分支都收缩掉。使得收缩后的图G满足∣S∣=∣E(G)∣且w(G-S)=∣V(G)∣。最后结合第一部分的结论可证得:G为3-边连通,基本5-边连通的图。若σ(G)≥8,则该图具有超欧拉性。
本文是在Yang[11]的定理上进行的推广,并且得到的结论与1995年Chen和Lai[4]的猜想很接近。