结合图的导出匹配可扩性(英文)  

Induced Matching Extendability of the Composition of Two Graphs

作　　者：原晋江[1] 周菊[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《郑州大学学报（理学版）》2004年第1期29-32,共4页Journal of Zhengzhou University:Natural Science Edition

基　　金：国家自然科学基金资助项目编号 10 3 71112;河南省自然科学基金资助项目

摘　　要：简单图 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中一个有完美匹配 ,另一个有几乎完美匹配 .The composition of simple graphs G and H is the simple graph G 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 G 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.

关 键 词：导出匹配 IM-可扩 几乎完美匹配 结合图 非平凡图 连通图 

分 类 号：O157.5[理学—数学]