| 结合图的导出匹配可扩性 |
| |
| 引用本文： | 原晋江,周菊.结合图的导出匹配可扩性[J].郑州大学学报(理学版),2004,36(1):29-32. |
| |
| 作者姓名： | 原晋江 周菊 |
| |
| 作者单位： | 郑州大学数学系,郑州,450052 |
| |
| 基金项目： | 国家自然科学基金，河南省自然科学基金 |
| |
| 摘 要： | 简单图G和H的结合图GH]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图GH]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则GH]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.
|
| 关 键 词： | 导出匹配 IM-可扩的 完美匹配 几乎完美匹配 结合图 |
Induced Matching Extendability of the Composition of Two Graphs |
| |
| Abstract.Induced Matching Extendability of the Composition of Two Graphs[J].Journal of Zhengzhou University:Natural Science Edition,2004,36(1):29-32. |
| |
| Authors: | Abstract |
| |
| Abstract: | The composition of simple graphs G and H is the simple graph GH] with vertex set V(G)×V(H),in which (u,v) is adjacent to (u′,v′) if and only if either uu′∈E(G) or u＝u′ and vv′∈E(H).The induced matching extendability of the composition of two graphs is studied.It is shown that GH] is IM-extendable,if both G and H are nontrivial,G is connected,and G and H satisfy one of the following conditions:(1) one of G and H is IM-extendable;(2) both G and H have perfect matchings;(3) one of G and H has a perfect matching and the other has a near perfect matching. |
| |
| Keywords: | induced matching IM-extendable perfect matching near perfect matching composition |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
