循环图中部分图类的导出匹配可扩性  

The Induced Matching Extendibility of some Graphs in Cyclic Graph

作　　者：全焕[1] 张晓东[2] 

机构地区：[1]平顶山工学院基础部,河南平顶山467001 [2]河南质量工程职业学院,河南平顶山467001

出　　处：《河南科学》2008年第1期15-18,共4页Henan Science

摘　　要：如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±k(mod2n)的i和j,均有xixj∈E(G,)则称其为步长为1和k的循环图,记为C2n(1,k.)通过详细讨论循环图的导出匹配可扩性,具体给出了循环图中的部分图类的导出匹配可扩性。A simple graph G is called as the induced matching extendable, if any induced matching of G can be included in a perfect matching of G. The cyclic graph which step length is 1 and k, denoted by C2n,（1,k）, is the graph with 2n vertices Xl,X2,……,x2n, such that x1xj is an edge of C2n（1 ,k） if either i-j = ±1 （mod 2n）or i-j =± k （mod 2n）. In this paper the induced matching extendibility of cyclic graph is discussed. We give the IM extendablity of some graohs in cyclic graphs.

关 键 词：导出匹配 完美匹配 可扩的 循环图 

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