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

摘要

如果一个图的任何一个导出匹配都能包含在一个完美匹配当中,就称之为导出匹配可扩的.对有2n个顶点x1,x2,…,x2n的图,如果对于i-j≡±1(mod 2n)或者i-j≡±n/2(mod 2n)的i和j,均有xixj∈E(G),则称其为步长为1和n/2的循环图,记为C2n(1,n/2).本文的主要结论为:C2n(1,n/2),n≥4,是导出匹配可扩的.