论文部分内容阅读
简单图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中一个有完美匹配，另一个有几乎完美匹配。