可扩图的一些性质

摘要：

设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)|≤4n-2,则对于任一u∈V(G),G[Γ(u)]都有一个基数为n的匹配.

关键词：匹配、n-可扩图、简单图

所属期刊栏目：34

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金60103021

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：15-18,25