匹配可扩图的结构

• 作 者: 张东艳 王世英 等
• 机 构: 晋中师专数学系,华中科技大学控制科学与工程系
• 出 处: 数学研究
• 发表日期: 2000年4期
• 关键词: n-可扩 障碍 CAYLEY图 匹配可扩图 结构 简单连通图 matching n-extendable barrier Cayley gra

设G是一个有限的简单连通图。D（G）表示V（G）的一个子集，它的每一个点至少有一个最大匹配不覆盖它。A（G）表示V（G）-D（G）的一个子集，它的每一个点至少和D（G）的一个点相邻。最后设C（G）=V（G）-A（G）-D（G）。在这篇文章中，下面的被获得。⑴设u∈V（G）。若n≥1和G是n-可扩的，则（a)C(G-u)=φ和A（G-u)∪{u}是一个独立集，（b)G的每个完美匹配包含D（G-u)的每个分支的一个几乎守美匹配，并且它匹配A（G-u)∪{u}的所有点与D（G-4）的不同分支的点。⑵若G是2-可