结合图的导出匹配可扩性

摘要：

简单图G和H的结合图G[H]的顶点集为V(G)×V(H),其中(u,v)和(u′,v′)相邻的充分必要条件是:或者uu′∈E(G)或者u＝u′并且vv′∈E(H).研究了结合图G[H]的导出匹配可扩性,证明了若G和H是非平凡图,G是连通图,且G和H满足下列条件之一,则G[H]是导出匹配可扩的:(1) G和H中有一个是导出匹配可扩的;(2) G和H都有完美匹配;(3) G和H中一个有完美匹配,另一个有几乎完美匹配.

关键词：导出匹配、IM-可扩的、完美匹配、几乎完美匹配、结合图

所属期刊栏目：36

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

资助基金：国家自然科学基金10371112;河南省自然科学基金

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

页数：共4页

页码：29-32