如果图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图.
A graph G is called supereulerian if G has a spanning eulerian subgraph. Let ar (G) be the maximum number of independent edges in the graph G. In this paper we show that if G is a 2-edge-connected simple graph and α'/(G) ≤2, then either G is collapsible, or there is a connected subgraph H of G such that the contraction G/H is K2,t for some positive integer t≥ 2. This strengthens the main result of [Lai H J, Yan H. Supereulerian graphs and matchings. Appl. Math. Lett., 2011, 24: 1867-1869]. We also verify a conjecture in the same paper above, that if G is a 3-edge-connected simple graph and α'(G) 〈 5, then G is supereulerian if and only if G is not contractible to the Petersen graph.