超欧拉图、可折叠图及匹配

来源：应用数学学报杂志2016年第6期北京时间：

作者：安明强, 熊黎明

单位：1. 北京理工大学数学与统计学院, 北京 100081;2. 天津科技大学理学院, 天津 300457

摘要：如果图G有一个生成的欧拉子图，则称G是超欧拉图.用α'（G）表示G中最大独立的边的数目.本文证明了：若G是一个2-边连通简单图且α'（G）≤2，则G要么是可折叠图，要么存在G的某个连通子图H，使得对某个正整数t≥2，约化图G/H是K2，t.推广了[Lai H J，Yan H.Supereulerian graphs and matchings.Appl.Math.Lett.，2011，24：1867-1869]中的一个主要结果.并且证明了上述文献中提出的一个猜想：3-边连通且α'（G）≤5的简单图是超欧拉图当且仅当它不可收缩成Petersen图.

关键词：超欧拉图,可折叠图,收缩,独立边

基金资助：国家自然科学基金（11471037）资助项目.