步长为1和4的2n阶循环图的导出匹配可扩性  

The induced matching extendability of cyclic graph with 2n vertices and step length 1 and 4

作　　者：徐华锋[1] 宋玉平 

机构地区：[1]平顶山工学院,河南平顶山467001 [2]平顶山中盐皓龙有限责任公司,河南平顶山467001

出　　处：《平顶山工学院学报》2004年第4期48-50,共3页Journal of Pingdingshan Institute of Technology

摘　　要：　研究了C2n(1,4)的导出匹配可扩性,得出主要结论:C2n(1,4)当n≥12和n=9时不是导出匹配可扩的,当3≤n<9和n=10,11时是导出匹配可扩的。We say that a simple graph G is induced matching extendable,shortly IM-extendable,if every induced matching of G is included in a perfect matching of G..The cyclic graph with 2n vertices which step length are 1 and 4,denoted by C_(2n)(1,4), is the graph with 2n vertices x_1,x_2,…x_(2n),such that x_ix_j is an edge of C_(2n)(1,4) if either｜i-j｜≡1(mod 2n) or ｜i-j｜≡4(mod 2n). We show in this paper,C_(2n)(1,4) for n≥12 and n=9 is not IM-extendable;but IM-extendable for 3≤n≤9 and n=10,11.

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

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