| 饱和二部图 |
| |
| 引用本文： | 张国志,王世英.饱和二部图[J].晋中学院学报,2010,27(3). |
| |
| 作者姓名： | 张国志 王世英 |
| |
| 作者单位： | 1. 晋中学院,数学学院,山西,晋中,030600
2. 山西大学,数学科学学院,太原,030006 |
| |
| 基金项目： | 山西省自然科学基金资助项目，国家自然科学基金资助项目 |
| |
| 摘 要： | 没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X(∈)V(G),T(X)表示V(G)中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=(U,W)是饱和的当且仅当(a)存在唯一X(∈)U,使得|X|＞Γ(X)|,|X|-1＞|Γ(X)|且G的导出子图GX∪Γ (X)]是完全二部图;(6)G的导出子图G(U-X)∪(W-Γ(X))]是完全二部图,且满足|U-X|+1=|W-Γ(X)|;(c)U-X中每个顶点与W中的每个顶点都相邻,且X∪(W-Γ(X))是图G的一个独立集.
|
| 关 键 词： | 饱和二部图 完美匹配 集合 |
Saturated Bipartite Graphs |
| |
| ZHANG Guozhi,WANG Shiying.Saturated Bipartite Graphs[J].Journal of Jinzhong University,2010,27(3). |
| |
| Authors: | ZHANG Guozhi WANG Shiying |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
