可扩图的一些性质  

Some Properties of Extendable Graphs

作　　者：王世英[1] 

机构地区：[1]山西大学数学系,太原030006

出　　处：《郑州大学学报（理学版）》2002年第4期15-18,25,共5页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家自然科学基金资助项目 ( 60 10 30 2 1)

摘　　要：设 G是一个连通的简单图且具有完美匹配 .如果 G的任一基数为 n(n≤ (|V(G) |-2 ) /2 )的匹配都能扩充为 G的一个完美匹配 ,则称 G为 n-可扩的 .对于 S V(G) ,记 M是 G[S]的基数为 r的最大匹配 ,并令 T=S-V(M) .对连通的非二部的 n-可扩图 G(n≥ 2 ) ,得到以下结果 :(1 )若 r≤ n且 |T|≥ 2 ,则 |V(G) |≥ 2 (n+r+|T|-1 ) .(2 )若 r≤ n-2且 |T|≥ 2 ,则 |V(G) |≥ 2 (n+r+|T|) .(3 )若|V(G) |≤ 4 n-2 ,则对于任一 u∈V(G) ,G[Γ(u) ]都有一个基数为Let G be a finite simple connected graph with a perfect matching. G can be extended to a perfect matching of G. The following results are obtained. Let SV(G) and M be a maximum matching of size r in G. Set T=S-V(M). (1) Let G be a connected n-extendable nonbipartite graph with n≥2. If r≤n and |T|≥2, then |V(G)|≥2(n+r+|T|-1). (2) Let G be a connected n-extendable nonbipartite graph with n≥2. If r≤n-2 and |T|≥2, then |V(G)|≥2(n+r+|T|). (3) Let G be a connected nonbipartite n-extendable graph with |V(G)|≤4n-2 and n≥2. Then for every u∈V(G), G has a matching of size n.

关 键 词：完美匹配 N-可扩图 简单图 简单图 最大匹配 基数 

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