偶匹配可扩图的度和连通度条件(英文)  

Degree sum and connectivity conditions for bipartite matching extendable graphs

作　　者：张文勇[1] 李晓玲[1] 赵飚[1] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）》2010年第4期408-412,共5页Journal of Xinjiang University(Natural Science Edition)

基　　金：supported by NSFC(No.10671165)

摘　　要：称图G是偶匹配可扩的,是指G的每一个导出二部偶子图的任意完美匹配都可以扩充为G的一个完美匹配.记δk(G)为一个k元独立集的最小度和,κ(G)为图G的连通度.在本文章中,给出了2n个顶点的图G满足κ(G)≥2(n/2)+1,和δ3(G) ≥ 3(3n/2)-2.那么G是偶匹配可扩的.并给出例子说明两个条件都是紧的.A graph G is said to be bipartite matching extendable if every matching M which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching of G. For a graph G, let δk（G） be the minimum degree sum of an independent set of k vertices, let K（G） be the connectivity of a graph G. In this paper, we prove that if G is a graph of order 2n with K（G） 〉 2“n/2” ＋ 1 and δ3（G）≥ 3 “3n/2”-2, then G is bipartite matching extendable graph. We also show that the bound for the conditions are almost the best possible.

关 键 词：偶匹配可扩图 完美匹配 度和 连通度 

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