步长为1和n/2循环图的导出匹配可扩性研究  

Study on the Induced Matching Extendibility of Cyclic Graph with Step Length 1 and 1/2

作　　者：徐华锋[1] 尹红征[2] 刘斌[2] 

机构地区：[1]平顶山工学院基础部,河南平顶山467001 [2]河南农业大学信息与管理科学学院,郑州450002

出　　处：《河南科学》2006年第5期638-640,共3页Henan Science

基　　金：河南省自然科学基金(02401180);河南省教育厅自然科学基金(200610466009)

摘　　要：如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod2n)或者i-j≡±n2(mod2n)的i和j,均有xixj∈E(G),则称其为步长为1和n2的循环图,记为C2n(1,2n).本文的主要结论为:C2n(1,2n),n#4,是导出匹配可扩的.A simple graph G is called as the 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 n/2, denoted by C2n （1, n/2）,is the graph with 2n vertices xl, x2 x…x2n, such that xixj is an edge of C2n（1,n/2） if either i-j=±1（mod 2n）or i-j=±n/2（mod 2n） It is shown that C2n（1, n/2） ,n≥ 4 is IM-extendable.

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

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