Induced Matching Extendability of the Composition of Two Graphs
2004-04-29 00:00:00YuanJinjiangZhouJu
鄭州大學學報(理學版) 2004年1期
Abstract：The composition of simple graphs G and H is the simple graph G[H]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[H]IS IM-extendable，if both G and H are nontrivial，G is connected，and G 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.
Key words：induced matching；IM-extendable；perfect matching；near perfect matcding；composition
CLC number：O 157.5
Artical ID：1671-6841(2004)01-0029-04
