The induced matching extendability of cyclic graph with 2n vertices and step length 1 and 4
XU Hua-feng · Journal of Pingdingshan Institute of Technology · 2004
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.