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

Supereulerian Graphs,Collapsible Graphs and Matchings

作　　者：安明强[1,2] 熊黎明[1] 

机构地区：[1]北京理工大学数学与统计学院,北京100081 [2]天津科技大学理学院,天津300457

出　　处：《应用数学学报》2016年第6期871-877,共7页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11471037)资助项目

摘　　要：如果图G有一个生成的欧拉子图,则称G是超欧拉图.用α′(G)表示G中最大独立的边的数目.本文证明了:若G是一个2-边连通简单图且α′(G)≤2,则G要么是可折叠图,要么存在G的某个连通子图H,使得对某个正整数t≥2,约化图G/H是K_(2.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.

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

分 类 号：O157.5[理学—数学]